HDU 1241 Oil Deposits

 1 #include <iostream>
 2 #include <cstdio>
 3 #define pf(x) printf("%d
", x)
 4 using namespace std;
 5 const int MAX = 105;
 6 char oil[MAX][MAX];
 7 int Move[8][2]= {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
 8 int m, n, ans;
 9 void DFS(int x, int y);
10 int main()
11 {
12     int i, j;
13     while(scanf("%d%d", &m, &n) != EOF, m || n)
14     {
15         ans = 0;
16         for(i = 0; i < m; i++)
17             scanf("%s", oil[i]);
18         for(i = 0; i < m; i++)
19             for(j = 0; j < n; j++)
20             {
21                 if(oil[i][j] == '@')//判断有无油田
22                 {
23                     oil[i][j] = '*';//标记该点已经走过
24                     ans++;
25                     DFS(i, j);//遍历的次数，一次则代表有一窝
26                 }
27             }
28         pf(ans);
29     }
30     return 0;
31 }
32 void DFS(int x, int y)
33 {
34     int i;
35     for(i = 0; i < 8; i++)
36     {
37         int xx = x + Move[i][0];
38         int yy = y + Move[i][1];
39         if(xx>=0 && xx<m && yy>=0 && yy<n && oil[xx][yy]=='@')//判断是否超出地图边界和是否可行
40         {
41             oil[xx][yy] = '*';//标记已经走过的点
42             DFS(xx,yy);//以此点为起点继续深入搜索,这就是深度优先搜索
43         }
44     }
45 }

View Code

若使用used[i][j]标记所走过的路径，则不方便（且需要注意if()语句中的条件）

#include <iostream>
#include <cstdio>
#include <cstring>
#define pf(x) printf("%d
", x)
using namespace std;
const int MAX = 105;
char oil[MAX][MAX];
int used[MAX][MAX];
int Move[8][2]= {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int m, n, ans;
void DFS(int x, int y);
int main()
{
    int i, j;
    while(scanf("%d%d", &m, &n) != EOF, m || n)
    {
        ans = 0;
        memset(used, 0, sizeof(used));
        for(i = 0; i < m; i++)
            scanf("%s", oil[i]);
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
            {
                if(!used[i][j] && oil[i][j] == '@')//判断有无油田
                {
                    used[i][j] = 1;//标记该点已经走过
                    ans++;
                    DFS(i, j);//遍历的次数，一次则代表有一窝
                }
            }
        pf(ans);
    }
    return 0;
}
void DFS(int x, int y)
{
    int i;
    for(i = 0; i < 8; i++)
    {
        int xx = x + Move[i][0];
        int yy = y + Move[i][1];
        if(!used[xx][yy] && xx>=0 && xx<m && yy>=0 && yy<n && oil[xx][yy]=='@')//判断是否超出地图边界和是否可行
        {
            used[xx][yy] = 1;//标记已经走过的点
            DFS(xx,yy);//以此点为起点继续深入搜索,这就是深度优先搜索
        }
    }
}