b701: 我的領土有多大

2019-08-21

內容

安安國是個島國，有大小不等的小島，身為地政首長的你想要瞭解每個島嶼的面積，以及每個島嶼的極點，如極北、極南、極東、極西。

現在你手上有 0、1 構成的地圖檔，0 代表海洋，1 代表陸地。陸地沒有相連的各視為獨立的小島

有一點點相連的，則視為同一小島

依照土地所在的位置，由北而南、由西而東順序顯示

請完成您的任務。

輸入

前面兩個數字 16 <=X<=512 16 <=Y<=512

分別代表地圖資料的 X 軸及 Y 軸長度

下方的地圖用 0 代表海洋，1 代表陸地。

16 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0
0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

輸出

每一塊土地輸出五個數字

W N E S A

分別代表極西、極北、極東、極南、面積

依照土地所在的位置，由上而下、由左而右順序顯示

4 2 12 9 36
2 11 4 14 7
9 11 13 13 9

解題思路

用迴圈找到陸地之後就用 DFS 由該地開始遍歷整個島，並將遍歷到的地方都改成海，如此一來於該次遍歷結束後整個島都會變成海，即可避免重複判斷到同一個島。

完整程式碼

AC (2ms, 156KB)

#include <stdio.h>

int map[515][515], x, y, r, l, u, d, a;

void dfs(int y, int x)
{
    a++;
    map[y][x] = 0;
    if (map[y][x - 1])
    {
        dfs(y, x - 1);
        if (l > x - 1)
            l = x - 1;
    }
    if (map[y][x + 1])
    {
        dfs(y, x + 1);
        if (r < x + 1)
            r = x + 1;
    }
    if (map[y + 1][x])
    {
        dfs(y + 1, x);
        if (d < y + 1)
            d = y + 1;
    }
    if (map[y - 1][x])
    {
        dfs(y - 1, x);
        if (u > y - 1)
            u = y - 1;
    }
}

int main()
{
    while (scanf(" %d %d", &x, &y) == 2)
    {
        for (int i = 1; i <= y; i++)
        {
            for (int j = 1; j <= x; j++)
                scanf(" %d", &map[i][j]);
        }
        for (int i = 1; i <= y; i++)
        {
            for (int j = 1; j <= x; j++)
            {
                if (map[i][j])
                {
                    l = j, u = i, r = j, d = i, a = 0;
                    map[i][j] = 0;
                    dfs(i, j);
                    printf("%d %d %d %d %d\n", l - 1, u - 1, r - 1, d - 1, a);
                }
            }
        }
    }
    return 0;
}