题意描述
输入多个m行n列的矩阵，用00表示输入结束。找出有多少块石油区域，用“@”代表石油，假如两个“@”在横，竖或对角线上相邻，就说它们位于同一区域，对于每个输入，输出一个数表示有几个石油区域。
输入
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
输出
0 1 2 2
思路:DFS
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 100+10; int m,n,book[maxn][maxn],cnt; char arr[maxn][maxn]; void dfs(int x,int y,int id){ if(x < 1 || x > m || y < 1 || y > n){//判断是否越界 return; } if(arr[x][y]!='@'||book[x][y]){//判断是否满足条件 (油田+未访问) return; } book[x][y] = id;//为每块油田进行编号 经过前面判断,说明当前这个油田符合条件 for(int i = -1; i<= 1; i++){ for(int j = -1; j <= 1; j++){ if(i!=0||j!=0){//方向坐标不能都为0 dfs(x+i,y+j,id);//继续访问 } } } } int main() { while(cin>>m>>n&&m&&n){ cnt = 0; memset(book,0,sizeof(book)); //memset(arr,'\0',sizeof(arr)); 这里可以不初始化,因为每一次地图都会被重新覆盖. for(int i = 1; i<=m; i++){ for(int j = 1; j <= n; j++){ cin>>arr[i][j]; } } for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(arr[i][j]=='@'&&!book[i][j]){ dfs(i,j,++cnt);//这里一定要是++cnt,编号要从1开始. } } } cout<<cnt<<endl; } return 0; }
