洛谷 1596.Lake Counting 5

英文题目最好自己翻译一下做，不要总是依赖中文翻译。

本道题和细胞数目一样，是一道典型的连通DFS问题。

思路：我们看准，这里说的是W是水，.是旱地。所以我们只遍历W连通的地方。

双层循环遍历这个地图，之后对于每一个枚举的点进行判断：

1.是不是水‘W’？

2.这里的点是不是被遍历过了？

然后我们就对于每一个点进行DFS遍历。对于DFS的函数来说，我们只需要判断这个点周围的点是不是水就行了，也就是周围这八个点，有个时候是4个点，我们需要灵活应变，这里的zoux和zouy就是对于方向的变化数组。

上代码:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 105
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int n, m, counts=0;
LL A, B;
int res = 0;
 
int st[MAX][MAX];
bool flag = false;
char maps[MAX][MAX];
int zoux[] = { -1,0,1,0,-1,-1,1,1};
int zouy[] = { 0,1,0,-1,1,-1,-1,1};
void dfs(int x, int y) {
 
        _for(i, 0, 8) {
            int a = x + zoux[i];
            int b = y + zouy[i];
            if (st[a][b])
                continue;
            if (a >= n || a < 0 || b >= m || b < 0)
                continue;
            if (maps[a][b] != 'W')
                continue;
 
            st[a][b] = 1;
            dfs(a, b);
        
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    _for(i, 0, n) {
        _for(j, 0, m) {
            cin >> maps[i][j];
        }
    }
    _for(i, 0, n) {
        _for(j, 0, m) {
            if (!st[i][j]&&maps[i][j]=='W') {
                st[i][j] = 1;
                dfs(i, j);
                res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}