首页 > 代码库 > DFS——hdu1241Oil Deposits

DFS——hdu1241Oil Deposits

一、题目回顾

题目链接:Oil Deposits

 

二、解题思路

  • DFS经典
  • 注意的就是要向八个方向搜索,搜索完一处,将该处变成石头。

 

三、代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int maxn = 1e4+10;
 7 #define INF 0x3f3f3f3f
 8 char a[105][105];            
 9 int m,n,k,ans;                         
10 
11 void dfs(int x,int y)        //当前坐标 
12 {
13     if(x<1 || x>m || y<1 || y>n || a[x][y]!=@){
14         return;
15     } 
16     a[x][y] = *;        //若(x,y)为石油,则标记已访问 
17     
18     //向当前坐标点的八个方向搜索 
19     dfs(x-1,y-1);
20     dfs(x,y-1);
21     dfs(x+1,y-1);
22     dfs(x-1,y);
23     dfs(x+1,y);
24     dfs(x-1,y+1);
25     dfs(x,y+1);
26     dfs(x+1,y+1);
27 }
28 int main()
29 {
30     while(cin>>m>>n && !(m==0 && n==0)){
31         for(int i=1;i<=m;i++){
32             getchar();
33             for(int j=1;j<=n;j++){
34                 scanf("%c",&a[i][j]);
35             }
36         }
37         getchar();
38         ans = 0;
39         for(int i=1;i<=m;i++){
40             for(int j=1;j<=n;j++){
41                 if(a[i][j] == @){
42                     dfs(i,j);
43                     ans++;
44                 }
45             }
46         }
47         printf("%d\n",ans);
48     }
49     return 0;
50 }

 

DFS——hdu1241Oil Deposits