例题6-12 油田(Oil Deposits, UVa 572)
欢迎访问我的Uva题解目录哦 https://blog.csdn.net/ri*qi/article/details/81149109
题目描述
题意解析
输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻(横、竖或者对角线方向),就说它们属于同一个八连块。
算法设计
用DFS找连通块,从每个“@”格子出发,递归遍历它周围的“@”格子。开辟一个二维数组visit
标记一个格子是否已被访问,这样就可以在访问之前检查它是否已经有了编号,从而避免同一个格子访问多次。
C++代码
#include<bits/stdc++.h>
using namespace std;
char oil[105][105];
bool visit[105][105];
int m,n;
void DFS(int i,int j){
visit[i][j]=true;
if(oil[i][j]=='@')
for(int ii=i-1;ii<=i+1;++ii)
for(int jj=j-1;jj<=j+1;++jj)
if(i>=0&&i<m&&j>=0&&j<n&&!visit[ii][jj]&&oil[ii][jj]=='@')
DFS(ii,jj);
}
int main(){
while(~scanf("%d%d%*c",&m,&n)&&m!=0){
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
scanf("%c",&oil[i][j]);
visit[i][j]=false;
}
getchar();
}
int num=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(!visit[i][j]&&oil[i][j]=='@'){
++num;
DFS(i,j);
}
printf("%d\n",num);
}
return 0;
}