poj 2386 Lake Counting (深度优先搜索基础)

题意：有一个大小为N×M的园子，雨后积起了水。八连通的积水被认为是连在一起的。求园子里一共有多少水洼？

 ****W*   （八连通指的就是左图中相对W的*的部分）***

Sample Input
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
Sample Output
3

解题思路：深度优先搜索，从任意的积水处(即W)开始，不停地把邻接的部分（八连通）用’.‘代替。1次DFS后与初始的这个W连接的所有W就都被替换成了’.’，因此直到图中不在存在W为止，总共进行DFS的次数就是答案。8个方向的共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂度为O(8×M×N）=O(M×N).

//深度优先搜索
#include<iostream>
using namespace std;
int n, m;
int mynext[8][2]{
    1,0,-1,0,1,1,-1,1,1,-1,-1,-1,0,1,0,-1
};
char map[101][101];
void DFS(int x, int y) {
    map[x][y] = '.';for (int i = 0; i < 8; i++) {
    int nx = x + mynext[i][0];int ny = y + mynext[i][1];if (nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == '.') {
     continue; }DFS(nx, ny);}return;
}
int main() {
    int ans = 0;cin >> n >> m;for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    cin >> map[i][j];}}for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    if (map[i][j] == 'W') {
    DFS(i, j);//cout << i << " " << j << endl;ans++;}}}cout << ans << endl;system("pause");return 0;
}