题目链接

题解:每个点(为被修改,是#)进行一次dfs,每次dfs到的点,也就是八个方向都将  '#'  修改成  '*',下次dfs就不用再搜索这一点了,因为已经确定这个点和前面的点是一个部分,这样遍历一遍图,如果可以dfs(i,j),ans++,最后ans就是答案了。当然也可以用bfs思路来想(点一下我QWQ)。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3;
int n,m;
char gra[maxn][maxn];
int dx[] = {1,1,1,-1,-1,-1,0,0};
int dy[] = {0,1,-1,1,0,-1,1,-1};
void dfs(int i, int j)
{
gra[i][j] = '*';
for(int k = 0; k < 8; k ++)
{
int tx = dx[k] + i;
int ty = dy[k] + j;
if(tx >= 0 && tx < n && ty >= 0 && ty < m && gra[tx][ty] == '@')
{
dfs(tx,ty);
}
}
}
int main()
{
int ans = 0;
while(~scanf("%d %d",&n,&m)&&n&&m)
{
ans = 0;
for(int i = 0; i < n; i ++)
{
getchar();
scanf("%s",gra[i]);
}
for(int i =0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(gra[i][j] == '@')
{
dfs(i,j);
ans ++;
}
}
}
printf("%d\n",ans);
}
return 0;
}
05-14 05:11
查看更多