[POJ] 2386 湖泊计数

• Reference
  • 湖泊计数 Lake Counting
• Problem

湖泊计数

时间限制：1000MS 内存限制：65536K

描述

由于最近的降雨，农夫约翰的田地里多处积水，田地由一个N×M（1<=N<=100；1<=M<=100）的矩形方格表示。每个方格都包含水（’W’）或旱地（’.’）。农民约翰想知道在他的田里有多少个池塘。一个池塘是一个有水的方格的连接集合，其中一个方格被认为与它的所有八个邻居相邻。

给出农夫约翰的田地图，确定他有多少个池塘。

输入

• 第1行： 两个隔开空间的整数： N和M
• 第2行…N+1： 每行M个字符，代表农夫约翰田地的一行。每个字符都是’W’或’.’。这些字符之间没有空格。
  输出
• 第1行： 农民约翰的田里有多少个池塘。

输入样本

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

有三个池塘：一个在左上方，一个在左下方，一个在右边。

• Code

#include <stdio.h>
#include <stdbool.h>

char Arr[101][101];
bool Flag[101][101];
int Dir[8][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}, {-1, 1}, {-1, -1}, {1, 1}, {1, -1}};
int a = 0;
int b = 0;
int Num = 0;

void handle(int i, int j)
{
    // printf("%d %d \n", i , j);
    if (i >= a || j >= b || i < 0 || j < 0 || Flag[i][j])
    {
        return;
    }
    Flag[i][j] = 1;

    for (int k = 0; k < 8; k++)
    {
        int x = i + Dir[k][0];
        int y = j + Dir[k][1];
        if (Arr[x][y] == 'W' && !Flag[x][y])
        {
            handle(x, y);
        }
    }

    return;
}

int main()
{

    scanf("%d %d\n", &a, &b);
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            scanf("%c", &Arr[i][j]);
        }
        getchar();
    }

    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            if (Arr[i][j] == 'W' && !Flag[i][j])
            {
                // printf("%d === %d=======\n", i, j);
                Num++;
                handle(i, j);
            }
        }
    }

    // for (int i = 0; i < a; i++)
    // {
    //     for (int j = 0; j < b; j++)
    //     {
    //         printf("%c", Arr[i][j]);
    //     }
    //     printf("\n");
    // }

    printf("%d\n", Num);
    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接