[POJ 2386]Lake Counting

Description

有一个大小为 N × M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼?(八连通指的是下图中相对 W 的*的部分)

* * *
* W *
* * *

Input

第 1 行 两个数 N, M
第2~n行 各 M 个数

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

题解

通过二维布尔表来记录积水,搜索邻接坐标的状态并重置以避免重复计数。

#include "cstdio"
#include "cmath"
#include "cstdlib"
#include "iostream"
#include "cstring"
#define INF 110
#define online
using namespace std;
int count = 0;
int n,m;
bool map[INF][INF];
inline bool handle(int n1,int m1,bool sign)
{
    //endowed W as 1, NULL and * as 0
    //use sign to distinguish the original requestion and derived requestion
    //True->Origin
    if (n1 < 0 || m1 < 0 || n1 >= n || m1 >= m)
    {
        #ifdef debug
        printf("n1 %d m1 %d n %d m %d out\n", n1, m1, n, m);
        #endif
        return 0;
    }
    if (map[n1][m1])
    {
        #ifdef debug
        printf("matched\n");
        #endif
        map[n1][m1] = 0;
        if (sign)
            count++;
        handle(n1,m1-1,0);
        handle(n1,m1+1,0);
        handle(n1+1,m1,0);
        handle(n1-1,m1,0);
        handle(n1-1,m1-1,0);
        handle(n1+1,m1+1,0);
        handle(n1+1,m1-1,0);
        handle(n1-1,m1+1,0);
    }

}

int main()
{
    //initialize
    scanf("%d%d", &n, &m);
    char c, str[m+1];
    memset(map,0,sizeof(map));
    //endowed * as 0, W as 1
    for (int i = 0; i < n; i++)
    {
        scanf("%s", &str);
        for (int j = 0; j < m; j++)
            map[i][j] = str[j] == '.' ? 0 : 1;

    }

    #ifdef debug
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            printf("%d", map[i][j]);
        printf("\n");
    }
    #endif

    //handle
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            handle(i,j,1);
    printf("%d\n", count);

    return 0;
}

CC BY-SA 4.0 [POJ 2386]Lake Counting by 小小泥娃 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.