UVA572-油田 Oil Deposits(DFS)

简介: UVA572-油田 Oil Deposits(DFS)


样例输入:


1 1

*

3 5

*@*@*

**@**

*@*@*

1 8

@@****@*

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

0 0


样例输出:


0

1

2

2


AC Code:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[101][101];//存入地图的数组 
int sum,n,m;
int vis[101][101];//标记数组 
int dx[]={-1,0,1,-1,1,-1,0,1};//题中说的是横、竖、对角线,所以有8个方向 
int dy[]={-1,-1,-1,0,0,1,1,1};
bool judge(int x,int y) {
  if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0&&s[x][y]=='@')//越界判断 
    return true;
  return false;
}
void dfs(int x,int y) {
  vis[x][y]=1;//标记访问过的每个点 
  for(int k=0;k<8;k++) {//8个方向搜索 
    int tx=x+dx[k];
    int ty=y+dy[k];
    if(judge(tx,ty)) {
      dfs(tx,ty);
    }
  }
}
int main() {
  while(~scanf("%d %d",&n,&m)) {//多实例输入 
    if(!n&&!m)//n和m均为0,输入结束 
      break;
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        scanf(" %c",&s[i][j]);//%前面的空格确保地图可以完整输入 
    memset(vis,0,sizeof(vis));//标记数组清零 
    sum=0;//油田数量 
    for(int i=0;i<n;i++) {
      for(int j=0;j<m;j++) {
        if(vis[i][j]==0&&s[i][j]=='@') {//此点未被访问,从找到的某个油田处开始搜索 
          sum++;//数量加1,并且搜索出与这个油田相连的所有油田,算1个石油区域 
          dfs(i,j);
        }
      }
    }
    printf("%d\n",sum);
  }
  return 0;
} 
相关文章
|
算法
1091 zoj Knight Moves的BFS算法和DFS
1091 zoj Knight Moves的BFS算法和DFS
60 0
POJ-2488,A Knight's Journey(DFS)
POJ-2488,A Knight's Journey(DFS)
HDOJ/HDU 1241 Oil Deposits(经典DFS)
HDOJ/HDU 1241 Oil Deposits(经典DFS)
87 0