题目描述
小杨有一个 𝑛 行 𝑚 列的网格图,其中每个格子要么是白色,要么是黑色。对于网格图中的一个子矩形,小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。
输入格式
第一行包含两个正整数 𝑛,含义如题面所示。
之后 𝑛 行,每行一个长度为 𝑚 的 01 串,代表网格图第 𝑖 行格子的颜色,如果为 0,则对应格子为白色,否则为黑色。
输出格式
输出一个整数,代表最大的平衡子矩形包含格子的数量,如果不存在则输出 0。
输入样例
4 5
00000
01111
00011
00011
输出样例
16
数据范围
对于全部数据,保证有 1≤𝑛,𝑚≤101≤n,m≤10。
---------------------------------------------------------------------------------------------------------------------------------
好的,题目现在是已经写完了,然后就是我们的思考环节
题目解析
首先我们要知道这道题他主要再问我们什么,注意看这句话“它是平衡的当且仅当其中黑色格子与白色格子数量相同”,他的意思是这必须是一个黑白格子相同的方形,不能多一个少一个的,关键是“代表最大的平衡子矩形包含格子”,他竟然还想让我找最大的,这不就,找对人了吗
方法一
1. 首先,定义一个大小为n*m的二维数组,表示黑白方块的布局。其中,黑色方块用数字1表示,白色方块用数字0表示。
2. 使用一个循环遍历数组的所有元素,判断当前格子是否为黑色方块。如果是黑色方块,则将其标记为已经访问过。如果是白色方块或者已经访问过的黑色方块,则跳过当前格子。
3. 定义一个变量count,用于记录黑色方块的数量。
4. 再次使用一个循环遍历grid数组的所有元素,对于每个黑色方块,使用深度优先搜索(DFS)或广度优先搜索(BFS)的方式,找到与其相连的所有黑色方块,将其标记为已访问过,并将count加一。
5. 返回count作为结果,即黑色方块的数量。
代码示例:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int countBlackBlocks(vector<vector<int>>& grid) {
int n = grid.size();
int count = 0;
vector<vector<bool>> visited(n, vector<bool>(n, false)); // 记录格子是否已访问过
// 遍历grid数组
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) { // 如果当前格子是黑色方块且未访问过
visited[i][j] = true; // 标记为已访问
count++;
// 使用BFS遍历与当前黑色方块相连的所有黑色方块
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int x = cur.first;
int y = cur.second;
vector<pair<int, int>> neighbors = {{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}};
for (pair<int, int> neighbor : neighbors) {
int nx = neighbor.first;
int ny = neighbor.second;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{1, 0, 1}, {0, 1, 0}, {1, 0, 1}};
int result = countBlackBlocks(grid);
cout << result << endl; // 输出结果:4
return 0;
}
```
以上代码使用广度优先搜索(BFS)的方式来统计黑色方块的数量。在深度优先搜索(DFS)的方式下,只需稍作修改即可。
以上是一种ai的解题思路
对于这道题,我有另一种方法
方法二
因为他有题目数据的限制的两个数都小于十,所以我们就能想到我们所熟知的一种方法
————枚举法
我们只需要通过枚举法不断地遍历,标记,最后在通过标记的位置来进行判断矩阵,最后输出一下这个矩阵的大小就行了,so~~~~~easy
具体的代码展示如下:
#include<iostream>
using namespace std;
int main()
{
int a[15][15],m,n,s;
s=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
a[i][j]=ch-'0';
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int ii=i;ii<=n;ii++)
{
for(int jj=j;jj<=m;jj++)
{
int g;
g=0;
for(int x=i;x<=ii;x++)
{
for(int y=j;y<=jj;y++)
{
g=g+a[x][y];
}
}
if (cnt*2==(ii-i+1)*(jj-j+1))
{
s=max(s,(ii-i+1)*(jj-j+1));
}
}
}
}
}
cout<<s<<endl;
return 0;
}
这种方法是我推荐的一种比较简单也是我们所熟知的一种方法,简单易懂。
好的题目我们现在是做完了
我是修勾,我们下期不见不散
我会持续跟新GESP的考级题目
5赞更!拜拜