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

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

题目描述
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

W........WW.

.WWW.....WWW

....WW...WW.

.........WW.

.........W..

..W......W..

.W.W.....WW.

W.W.W.....W.

.W.W......W.

..W.......W.

Sample Output

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

C++ 代码

#include <iostream>

#include <set>

using namespace std;

#define MAX_NUM 110

int N, M;

char field[MAX_NUM+][MAX_NUM + ];

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=;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 - ;

    if (xcopy >=  && x < N) {

        for (int add = -; add <= ; add++) {

            int ycopy = y + add;

            if (ycopy >=  && ycopy < M && field[xcopy][ycopy] == 'W') {

                int idx = x * M + y;

                int anotherIdx = xcopy * M + ycopy;

                merge(idx, anotherIdx);

            }

        }

    }

    //中

    xcopy = x;

    if (xcopy >=  && x < N) {

        for (int add = -; add <= ; add++) {

            if (add == ) continue;

            int ycopy = y + add;

            if (ycopy >=  && ycopy < M && field[xcopy][ycopy] == 'W') {

                int idx = x * M + y;

                int anotherIdx = xcopy * M + ycopy;

                merge(idx, anotherIdx);

            }

        }

    }

    //下

    xcopy = x + ;

    if (xcopy >=  && x < N) {

        for (int add = -; add <= ; add++) {

            int ycopy = y + add;

            if (ycopy >=  && 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 = ; i < N; i++) {

        for (int j = ; j < M; j++) {

            cin >> field[i][j];

            if (field[i][j] == 'W') {

                //检查上下左右八个方向是否有坑

                Check(i,j);

            }

        }

    }

    set<int> s;

    for (int i = ; i < N; i++) {

        for (int j = ; 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 ;

}

作者：defddr

链接：https://www.acwing.com/solution/acwing/content/3674/

来源：AcWing

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

C++ 代码

#include <iostream>

using namespace std;

int N, M;

int unitCount = ;

#define MAX_NUM 110

char field[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','.'},

//    {'.','.','W','.','.','.','.','.','.','.','W','.'}

//};

void Dfs(int x, int y)

{

    //终止条件

    if (x <  || x >= N || y <  || y >= M || field[x][y] == '.')

        return;

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

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

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

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

}

int main()

{

    cin >> N >> M;

    //N = 10; M = 12;

    for (int i = ; i < N; i++) {

        for (int j = ; j < M; j++) {

            cin >> field[i][j];

        }

    }

    for (int i = ; i < N; i++) {

        for (int j = ; j < M; j++) {

            if (field[i][j] == 'W'){

                unitCount++;

                Dfs(i,j);

            }

        }

    }

    cout << unitCount << endl;

    return ;

}

巴特西

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

最新文章

热门文章