注意!注意!注意!
要加边界判定, 最外面一层有岛屿!!!
#include <iostream>
using namespace std;
const int N = 1010;
int n;
char d[N][N];
bool st[N][N];
int res;
bool flag;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y)
{
st[x][y] = true;
bool ret = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && nx >= 1 && ny <= n) // 要判断边界
{
if (d[nx][ny] == '.')
ret = false;// 如果周围有水的话就表示被淹了
}
}
if (ret)
flag = true;
if (d[x - 1][y] == '#' && d[x + 1][y] == '#' && d[x][y - 1] == '#' && d[x][y + 1] == '#')
flag = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && nx >= 1 && ny <= n)
{
if (!st[nx][ny] && d[nx][ny] == '#')
dfs(nx, ny);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> d[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (!st[i][j] && d[i][j] == '#')
{
flag = false;
dfs(i, j);
if (!flag)
res += 1;
}
}
cout << res << endl;
system("pause");
return 0;
}
0 回复
0 转发
1 喜欢
4 阅读



