Lake Counting

Lake Counting （ POJ No.2386）
有一个大小为 N×M 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼？（八连通指的是下图中相对 W 的.的部分）
其中W是积水，.是干地

…
.W.
…

限制条件
 N, M ≤ 100

输入样例:

N=10, M=12
园子如下图（’W’表示积水， ‘.’表示没有积水）
W……..WW.
.WWW…..WWW
….WW…WW.
………WW.
………W..
..W……W..
.W.W…..WW.
W.W.W…..W.
.W.W……W.
..W…….W.

输出：
3

解题思路： 刚开始看这道题的时候，是不太理解它的意思的，或者说可能会被给的那个八连通例子给误导，认为只能那样的状态才是水洼。其实这道题的本质是让你求极大连通图的个数，就好像是广场中的积水被干地分为了3块，互相都不连通，但是块内是可以连通的，就这个意思。所以，我们以任意一个W进行上、下、左、右、左上、右上、左下、右下。遇到W就替换成’.’，标记为遍历过了。当遇到的W的周围八个点都没有积水，那么一个极大连通图就出来了，以此类推求出所有满足的要求的个数。

代码：

#include <iostream>
#include <vector>
using namespace std;

//深度优先搜索,从x,y这一点向周围八个点搜索
void DFS(vector<vector<char> >& g,int n,int m,int x,int y)
{
    //每次向周围搜索前，先将x,y这点置为'.',可以理解为遍历过就当作是干地，下次不再遍历
    g[x][y] = '.';
    //向周围八个点开始搜索
    for (int  i = -1; i <= 1; i++) //i = -1的意思是，从(x,y)点的最左边开始搜索
    {
        for (int j = -1; j <= 1; j++) //j = -1 的意思是，从(x,y)点的最上边开始搜索
        {
            //先判断是否超过范围，再判断是否是水池‘W’，如果是，则以这一点继续深搜
            if (x + i >= 0 && x + i < n && y + j >= 0 && y + j < m && g[x + i][y + j] == 'W')
                DFS(g, n, m, x + i, y + j);
        }
    }

}

//求水洼数量
int LakeCounting(vector<vector<char> >& g,int n,int m)
{
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (g[i][j] == 'W')
            {
                DFS(g,n,m,i,j); //这里的DFS调用相当于搜索极大连通图，DFS里面的是小连通图
                ++res;          //极大连通图的数量就是水洼的数量
            }
        }
    }
    return res;
}

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    vector<vector<char> > g(n);
    //输入
    for (int i = 0; i < n; i++)
    {
        g[i].resize(m);
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    }
    //输出
    cout << LakeCounting(g,n,m) << endl;


    return 0;
}

求极大联通图的过程，如下图所示：

和原图相比：

这就是那三个极大连通图。

最后求帮顶一下新博客ACME