$$\color{Purple}{kuangbin题解目录}$$
描述
一片土地可以看作是一个 $n$ 行 $m$ 列的方格矩阵。
其中一些方格藏有石油,用 @
表示,其余方格没有石油,用 *
表示。
每个方格都与其上、下、左、右、左上、右上、左下、右下八个方格视为相邻。
如果两个藏有石油的方格相邻,则它们被认为是处于同一片油田,否则它们被认为是处于不同油田。
请问,该土地中共有多少片油田。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $n$ 行,包含一个 $n$ 行 $m$ 列的字符矩阵,表示土地情况。
当输入一行 0 0
时,表示输入结束。
输出格式
每组数据输出一行,一个整数,表示油田数量。
数据范围
最多包含 $100$ 组数据。
$1 \\le n,m \\le 100$。
输入样例:
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
输出样例:
0
1
2
2
思路
基于bfs的思想,一次枚举没有标记的石油方格,枚举的次数即为答案.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAXN 110
using namespace std;
int n,m,cnt;
char g[MAXN][MAXN];
int vis[MAXN][MAXN];
struct node{
int x;
int y;
};
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
void bfs(int x,int y)
{
queue<node> q;
q.push({x,y});
vis[x][y]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
for(int i=0;i<=7;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&vis[dx][dy]==0&&g[dx][dy]=='@')
{
q.push({dx,dy});
vis[dx][dy]=1;
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
memset(vis,0,sizeof(vis));
cnt=0;
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(g[i][j]=='@'&&vis[i][j]==0)
bfs(i,j),cnt++;
printf("%d\n",cnt);
}
return 0;
}