题目描述

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式
第一行包含两个整数 N 和 M。

接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式
输出一个整数，表示池塘数目。

数据范围
1≤N,M≤1000
输入样例：
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

算法1

算法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;
}

算法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;
}