POJ 2386 Lake Counting 题解《挑战程序设计竞赛》

地址 http://poj.org/problem?id=2386

《挑战程序设计竞赛》习题

题目描述
Description

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John’s field, determine how many ponds he has.

Input

Line 1: Two space-separated integers: N and M

Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.
Output

Line 1: The number of ponds in Farmer John’s field.

样例

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

算法1
将相同的水坑算在一起 并查集

C++ 代码

#include <iostream>
#include <set>

using namespace std;

#define MAX_NUM 110

int N, M;
char field[MAX_NUM+10][MAX_NUM + 10];
int fa[MAX_NUM*MAX_NUM];

//char field[10][12] = {
//  {'W','.','.','.','.','.','.','.','.','W','W','.'},
//  {'.','W','W','W','.','.','.','.','.','W','W','W'},
//  {'.','.','.','.','W','W','.','.','.','W','W','.'},
//  {'.','.','.','.','.','.','.','.','.','W','W','.'},
//  {'.','.','.','.','.','.','.','.','.','W','.','.'},
//  {'.','.','W','.','.','.','.','.','.','W','.','.'},
//  {'.','W','.','W','.','.','.','.','.','W','W','.'},
//  {'W','.','W','.','W','.','.','.','.','.','W','.'},
//  {'.','W','.','W','.','.','.','.','.','.','W','.'},
//  {'.','.','W','.','.','.','.','.','.','.','W','.'}
//};


//===============================================
// union find
void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);//路径压缩,防止链式结构
}
void merge(int x,int y)
{
    fa[get(x)]=get(y);
}
//===========================================================



void Check(int x,int y)
{
    //上
    int xcopy = x - 1;
    if (xcopy >= 0 && x < N) {
        for (int add = -1; add <= 1; add++) {
            int ycopy = y + add;
            if (ycopy >= 0 && ycopy < M && field[xcopy][ycopy] == 'W') {
                int idx = x * M + y;
                int anotherIdx = xcopy * M + ycopy;
                merge(idx, anotherIdx);
            }
        }
    }

    //中
    xcopy = x;
    if (xcopy >= 0 && x < N) {
        for (int add = -1; add <= 1; add++) {
            if (add == 0) continue;
            int ycopy = y + add;
            if (ycopy >= 0 && ycopy < M && field[xcopy][ycopy] == 'W') {
                int idx = x * M + y;
                int anotherIdx = xcopy * M + ycopy;
                merge(idx, anotherIdx);
            }
        }
    }


    //下
    xcopy = x + 1;
    if (xcopy >= 0 && x < N) {
        for (int add = -1; add <= 1; add++) {
            int ycopy = y + add;
            if (ycopy >= 0 && ycopy < M && field[xcopy][ycopy] == 'W') {
                int idx = x * M + y;
                int anotherIdx = xcopy * M + ycopy;
                merge(idx, anotherIdx);
            }
        }
    }
}


int main()
{
    cin >> N >> M;
    //N = 10; M = 12;

    init(MAX_NUM*MAX_NUM);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> field[i][j];
            if (field[i][j] == 'W') {
                //检查上下左右八个方向是否有坑
                Check(i,j);
            }
        }
    }
    set<int> s;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (field[i][j] == 'W') {
                int idx = i * M + j;
                //cout << "fa["<<idx << "] = "<< fa[idx] << endl;
                s.insert(get(idx));
            }
        }
    }

    cout << s.size() << endl;

    return 0;
}


作者：defddr
链接：https://www.acwing.com/solution/acwing/content/3674/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法2
DFS 遍历 将坐标连续的坑换成. 计数+1

C++ 代码

#include <iostream>

using namespace std;

int N, M;
int unitCount = 0;

#define MAX_NUM 110

char field[MAX_NUM + 10][MAX_NUM + 10];

//char field[10][12] = {
//    {'W','.','.','.','.','.','.','.','.','W','W','.'},
//    {'.','W','W','W','.','.','.','.','.','W','W','W'},
//    {'.','.','.','.','W','W','.','W','W','W','W','.'},
//    {'.','.','.','.','.','.','.','.','.','W','W','.'},
//    {'.','.','.','.','.','.','.','.','.','W','.','.'},
//    {'.','.','W','.','.','.','.','.','.','W','.','.'},
//    {'.','W','.','W','.','.','.','.','.','W','W','.'},
//    {'W','.','W','.','W','.','.','.','.','.','W','.'},
//    {'.','W','.','W','.','.','.','.','.','.','W','.'},
//    {'.','.','W','.','.','.','.','.','.','.','W','.'}
//};


void Dfs(int x, int y)
{
    //终止条件
    if (x < 0 || x >= N || y < 0 || y >= M || field[x][y] == '.')
        return;

    field[x][y] = '.';

    Dfs(x + 1, y - 1); Dfs(x + 1,y); Dfs(x + 1, y + 1);
    Dfs(x , y-1);                Dfs(x , y + 1);
    Dfs(x -1, y-1); Dfs(x - 1, y); Dfs(x - 1, y +1);

}

int main()
{
    cin >> N >> M;
    //N = 10; M = 12;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> field[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (field[i][j] == 'W'){
                unitCount++;
                Dfs(i,j);
            }
        }
    }

    cout << unitCount << endl;

    return 0;
}