痛点
没有y总的帮助太痛了!这才是最大的痛点!
-
首先应该容易想到dfs或bfs很适合这样的地图题(我就按dfs为例了)
-
其次,最开始可能会想到dfs岛屿,但是怎么确定再次遍历到起点时,是走过了完整一圈,还是如直接在开始掉头的其他情况。解决这个问题又要想,如果不是完整一圈,又该从哪继续遍历其漏水的”内部“,如果是完整一圈,又要考虑它的左右上下边界从哪再继续找,似乎两种情况都巨麻烦。
-
所以,正难则反,我们可以先遍历海洋能流到哪:
首先标记一下哪里走过了不用走了,没走过就会有海洋和陆地两种情况:
1. 如果碰到了陆地,我再把这整个岛屿遍历一遍,标记这个岛屿已经被计数过了
2. 如果碰到的还是海洋,继续向“各个”方向流即可
- 注意了,这里海洋的各个方向是包括右上等的共八个方位,因为只有岛屿是上下左右四方时才算一座岛,所以海洋是能顺着“缝隙”流进去
这样就很巧妙的忽略掉岛中岛,因为从边缘出发的水流根本“渗透”不进去!
- 还有一个小问题,就是输入的时候如果int g[i][j]的常规遍历法只会把第一行的“01111”读入到g[0][1]上,所以如何输入单个数字也要注意。
我就是因为这个疯狂debug。。。
更多小细节请看注释,基本都是错过几次的地方,哭。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 55;
int m, n, res;
int g[N][N];
bool st[N][N];
int dx_land[4] = { -1,0,1,0 }, dy_land[4] = { 0,1,0,-1 };
void dfs_land(int x, int y) // 遍历陆地
{
st[x][y] = true;
for (int i = 0; i < 4; i++)
{
int a = x + dx_land[i];
int b = y + dy_land[i];
if (g[a][b] == 1 && !st[a][b]) dfs_land(a, b);
}
}
int dx_oc[8] = { -1,0,1,0,1,1,-1,-1 }, dy_oc[8] = { 0,-1,0,1,1,-1,-1,1 };
void dfs_oc(int x, int y) // 遍历海洋
{
st[x][y] = true;
for (int i = 0; i < 8; i++)
{
int a = x + dx_oc[i];
int b = y + dy_oc[i];
if (a<0 || a>m+1 || b<0 || b>n+1) continue; // 越界,多留条边让海洋即使中间被阻隔也能流到对岸
if (st[a][b]) continue; // 海洋遍历过
if (g[a][b] == 1) // 碰到陆地
dfs_land(a, b), res++;
else if (g[a][b] == 0) dfs_oc(a, b); // 是海洋就继续dfs
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
res = 0, memset(g, 0, sizeof g), memset(st, 0, sizeof st);
scanf("%d%d", &m, &n);
getchar(); // 清除数字末尾的回车
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
char t = getchar();
g[i][j] = t - '0';
}
getchar(); //清除每行末尾的回车
}
dfs_oc(0, 0); //从地图外开始,防止第一个就是1
printf("%d\n", res);
}
return 0;
}