思路
题意就是有一大片地方，让你去找里面有多少片油田(八个方向)，我们只需要遍历地图，当找到'@'的时候进行dfs，把搜索到的'@'都变成'*'就好了，然后用一个变量进行计数。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
char MAP[MAXN][MAXN];
int dir[8][2] = {1,0, 0,1, -1,0, 0,-1, 1,1, -1,1, -1,-1, 1,-1}; // 因为有8个方向
int n,m;
int sum;
void dfs(int x,int y){
MAP[x][y] = '*'; // 把搜索到的油田标记成空地
for(int i=0;i<8;i ){ // 8个方向搜索
int X = x dir[i][0];
int Y = y dir[i][1];
if(X >= 0 && Y >= 0 && X < n && Y < m && MAP[X][Y] == '@'){
dfs(X,Y);
}
}
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) break;
memset(MAP,0,sizeof(MAP));
for(int i=0;i<n;i ){ // 给地图赋值
scanf("%s",MAP[i]);
}
sum = 0; // sum记得清零
for(int i=0;i<n;i ){
for(int j=0;j<m;j ){
if(MAP[i][j] == '@'){ // 遍历到油田时进行搜索
dfs(i,j);
sum ; // 计数
}
}
}
printf("%dn",sum);
}
return 0;
}
/***
[来源] UVa 572
[题目] Oil Deposits
[大意]
经典的DFS题，这个就是求有多少片油田，只要8个方向连在一起的就是一片
所以只需要遍历地图，当找到一个油田时进行搜索，把搜索到的油田都变成
空地就好了。详细看代码注释。
[输入]
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
[输出]
0
1
2
2
*/
