ACM-DFS:POJ 2386 Lake Counting

为简化文章，原题请直接看原题链接

题意简要概括

在一个字符矩阵中，字符为'W'时，表示该处有水。该'W'与其周围的八个位置相通，如下面所示。一个水潭由其包含的所有相通的'W'构成。

...
.W.
...

输入

第一行给出两个参数n和m
第二行到第n=1行：每行给出m个元素，该元素或者为'W'或者为'.'

输出

输出计算水潭的个数

示例数据

输入：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出：

3

解题思路一（失败）：

初始化访问数组中元素皆为未访问
初始化输出结果ans为0
将数据输入字符数组

• 遍历字符数组中所有元素
  • 如果该元素为'W'且未访问
    • 将该元素入栈
    • 当栈不为空时
      • 出栈栈顶元素，标记为已访问，检查其八个方向的元素，如果为'W'且未访问，则入栈
      • ans++
  • 输出 ans

以下为失败代码

#include<iostream>
#include<stack>
using namespace std;
    int n,m;
    char mark[1005][1005];
    bool is[1005][1005]={false};
    struct Node{
        int x;
        int y;
        void set(int ax,int ay){
            x = ax;
            y = ay;
        }
    }; 
    stack<Node> s;

    int main(){
        Node work;
        int ans = 0;
        cin>>n>>m;
        for(int i = 0;i<n;++i)
            for(int j = 0;j<m;++j)
                cin>>mark[i][j];
        for(int i = 0;i<n;++i)
            for(int j = 0;j<m;++j){
                cout<<i<<" "<<j<<" "<<mark[i][j]<<endl;
                if(mark[i][j]=='W'&&!is[i][j]){
                is[i][j]==true;
                work.set(i,j);
                s.push(work);
                while(!s.empty()){
                    work = s.top();
                    s.pop();
                    cout<<"mark: "<<work.x<<" "<<work.y<<" "<<mark[work.x][work.y]<<endl;
                    is[work.x][work.y] = true; 
                    if(work.x-1>=0&&mark[work.x-1][work.y]=='W'&&!is[work.x-1][work.y]){
                        is[work.x-1][work.y] = true;
                        work.set(work.x-1,work.y);
                        s.push(work);
                    }
                    if(work.x-1>=0&&work.y-1>=0&&mark[work.x-1][work.y-1]=='W'&&!is[work.x-1][work.y-1]){
                        is[work.x-1][work.y-1] = true;
                        work.set(work.x-1,work.y-1);
                        s.push(work);
                    }
                    if(work.x-1>=0&&work.y+1<m&&mark[work.x-1][work.y+1]=='W'&&!is[work.x-1][work.y+1]){
                        is[work.x-1][work.y+1] = true;
                        work.set(work.x-1,work.y+1);
                        s.push(work);
                    }
                    if(work.y-1>=0&&mark[work.x][work.y-1]=='W'&&!is[work.x][work.y-1]){
                        is[work.x][work.y-1] = true;
                        work.set(work.x,work.y-1);
                        s.push(work);
                    }
                    if(work.y+1<m&&mark[work.x][work.y+1]=='W'&&!is[work.x][work.y+1]){
                        is[work.x][work.y+1] = true;
                        work.set(work.x,work.y+1);
                        s.push(work);
                    }
                    if(work.x+1<n&&mark[work.x+1][work.y]=='W'&&!is[work.x+1][work.y]){
                        is[work.x+1][work.y] = true;
                        work.set(work.x+1,work.y);
                        s.push(work);
                    }
                    if(work.x+1<n&&work.y-1>=0&&mark[work.x+1][work.y-1]=='W'&&!is[work.x+1][work.y-1]){
                        is[work.x+1][work.y-1] = true;
                        work.set(work.x+1,work.y-1);
                        s.push(work);
                    }
                    if(work.x+1<n&&work.y+1<m&&mark[work.x+1][work.y+1]=='W'&&!is[work.x+1][work.y+1]){
                        is[work.x+1][work.y+1] = true;
                        work.set(work.x+1,work.y+1);
                        s.push(work);
                    }
                }
                ++ans;
                }
            }
        cout<<ans<<endl;
        return 0;
    }

解题思路二（成功）

将数据输入字符数组
初始化输出结果ans为0

遍历字符数组的每一个元素
如果该元素为'W',位置为(i,j)，则DFS(i,j)，且ans++

DFS(i,j)
将（i,j）位置上的元素改为'.'
检查其八个方向的元素是否为‘W’,其位置为(g,k),如果是则DFS(g,k)

AC代码如下：

    #include<iostream>
    #include<stack>
    using namespace std;
    int n,m;
    char mark[1005][1005];
    void dfs(int i,int j){
        mark[i][j] = '.';
        for(int p = -1;p<=1;++p)
            for(int k = -1;k<=1;++k)
                if(mark[i+p][j+k]=='W')dfs(i+p,j+k);
    }
    int main(){
        int ans = 0;
        cin>>n>>m;
        for(int i =0;i<n;++i)
            for(int j =0;j<m;++j)
                cin>>mark[i][j];
        for(int i = 0;i<n;++i)
            for(int j = 0;j<m;++j)
                if(mark[i][j]=='W'){
                dfs(i,j);
                ans++;
                }
        cout<<ans<<endl;
        return 0;
    }