Uva 572 超经典无难度dfs

一、题意

有若干组数据。
每组数据第一行一个n和一个m.
接下来是一个n行m列的油田，要你输出油田中有多少个@块（斜着联通也算）。

二、解析

简单的dfs题目。用vis[maxn][maxm]维护每个点是否走过，然后进行dfs。
该题只是为了简单的复习一下dfs，没有啥难度。

三、代码

#include <iostream>
#include <string>
using namespace std;
const int maxn = 100 + 5, maxm = 100 + 5;
const int Fx[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
string a[maxn];
int n, m;
bool vis[maxn][maxm];

void dfs(int x, int y) {
    vis[x][y] = 1;
    for(int k = 0; k < 8; k ++) {
        int nx = x + Fx[k][0], ny = y + Fx[k][1];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || a[nx][ny] == '*') continue;
        dfs(nx, ny);
    }
}

int main() {
    while(cin >> n >> m && (n || m)) {
        for(int i = 0; i < n; i ++) cin >> a[i], fill(vis[i], vis[i] + m, 0);
        int cnt = 0;
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) if(a[i][j] == '@' && !vis[i][j]) dfs(i, j), cnt ++;
        }
        cout << cnt << endl;
    }
}

四、归纳

• dfs要领：用vis数组维护是否走过，记得清零；dfs中continue的条件分三类，即出界、已走过、不是所求。不要遗漏了。