Lakes

The Problem 

A region of two-dimensional space is divided by a grid into uniform square cells, each of which represents either "land" or "water".

We are interested in finding the area of a region of horizontally or vertically connected "water" cells totally enclosed by a boundary of "land" cells, given the location of a "water" cell in the region.

Choose a representation, such as a two-dimensional array, in which the basic operations available are to determine whether a cell is "land" or "water", and to move from a cell to any of its neighbors. Assume that you are given the location of an arbitrary "water" cell in the region whose area is required.

Since the area of the "water" region is defined to be the number of cells in it, the most straightforward way to compute the area is to simply count the number of cells in it. Write a program to do this.

The following restrictions and assumptions apply:

• the grid, G[1..M,1..N], is rectangular and is no larger than 99 by 99.
• an input of 0 (zero) represents water.
• an input of 1 represents land.
• there may be more than one body of water.
• the input is assumed to be surrounded by a "border" of land (1's)

Input 

The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.

line 1 -	two integers (i,j) separated by 1 blank which represents the position (row, column) of a "water" cell in the region whose area is to be determined. The input integers will be in character form; two non-blank characters followed by a blank followed by two more characters with the characters in [0, 1, ..., 9]
line 2 -	the first row of the grid (<=99 characters, all 1's or 0's) where the first character represents G[1,1], the second G[1,2], the third G[1,3], ...
line 3 -	the second row of the grid (<=99 characters, all 1's or 0's) where the first character represents G[2,1], the second G[2,2], the third G[2,3], ...
remaining lines for the remaining rows of the grid

Output 

For each dataset, display on a line of its own one integer which is the area of the enclosed area of water. Print a blank line between datasets.

Sample Input 

        1
        
        02 01
        1001101
        0011111
        0001001
        1100011
        1111111
        1100110
        1110111

Interpretation

          012345678
        0 LLLLLLLLL
        1 LLWWLLWLL
        2 LWWLLLLLL
        3 LWWWLWWLL
        4 LLLWWWLLL
        5 LLLLLLLLL
        6 LLLWWLLWL
        7 LLLLWLLLL
        8 LLLLLLLLL

Sample Output 

        12

---

找連通元件大小。

以下代碼使用 dfs，同理 bfs 也可以。

#include <stdio.h>
#include <string.h>
char g[105][105], used[105][105];
int n, m, res;
void dfs(int x, int y) {
    if(x < 0 || y < 0 || x >= n || y >= m)
        return;
    if(g[x][y] == '1' || used[x][y])
        return;
    used[x][y] = 1;
    res++;
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
}
int main() {
    int t, x, y;
    scanf("%d", &t);
    while(getchar() != '\n');
    gets(g[0]);
    while(t--) {
        gets(g[0]);
        memset(used, 0, sizeof(used));
        sscanf(g[0], "%d %d", &x, &y);
        n = 0, m;
        while(gets(g[n]) && g[n][0])
            n++;
        m = strlen(g[0]);
        res = 0;
        dfs(x-1, y-1);
        printf("%d\n", res);
        if(t)
            puts("");
    }
    return 0;
}
/*
1

02 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111
*/