题目描述
板子是flood fill求连通块
和之前题目不同的地方:
- 数字比较,而不是以往的两种字符比较。所以dfs传参要加上一个参数用于比大小
- dfs里面先判断点是否在边界内部,然后讨论每一个连通块的边界情况:如果周围有和它等大小的且还没被访问到,那么它是连通块的一部分,继续访问它;如果有大小关系,就用两个smaller和bigger两个变量存一下。
这里值得说的是,一开始我没想出来怎么判断一个连通块周围的块是否有大有小,后来发现了,只要用上述两个变量存一下就可以了,如果大小关系一致,那么一定有一个是0;如果两个都是0,嘿嘿就是整张图是一个连通块的特殊情况。
另外,这里判断大小关系确实会出现重复判断的问题造成耗时,我一开始想再开一个数组来存周围位置是否已经被访问过,但是发现没必要。
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n;
int g[N][N], t[N][N];
int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[] = {1, -1, 1, 0, -1, 1, 0, -1};
int low = 0, high = 0;
bool bigger = false, smaller = false;
void dfs(int x, int y, int k)
{
t[x][y] = 1;
for (int i=0; i<8; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < n)
{
if (g[a][b] < k)
bigger = true;
else if (g[a][b] > k)
smaller = true;
else if (g[a][b] == k && !t[a][b])
dfs(a, b, k);
}
}
}
int main()
{
scanf("%d", &n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
scanf("%d", &g[i][j]);
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (!t[i][j])
{
dfs(i, j, g[i][j]);
if (smaller && !bigger)
low++;
else if (bigger && !smaller)
high++;
else if (!bigger && !smaller)
{
high = 1;
low = 1;
}
bigger = false;
smaller = false;
}
}
}
printf("%d %d", high, low);
return 0;
}