Uva722 - Lakes

題目大意

一個二維空間中含有 water 與 land (空間被 land 所圍住)，我們需要從給定的座標開始，尋找此水域的面積。

重點觀念

分析

• 直接 bfs 或 dfs
• 雷點：
  • 輸入格式蠻麻煩的
  • 輸出最後一行不用兩個換行

程式題目碼

#include <cstring>
#include <iostream>
using namespace std;

char graph[100][100];
bool used[100][100];
int count;

void dfs(int i, int j) {
    if (i < 0 || j < 0 || i > 99 || j > 99) {
        return;
    }
    if (used[i][j] || graph[i][j] == '1' || !graph[i][j]) {
        return;
    }
    used[i][j] = true;
    count++;
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    while (n--) {
        int i, j;
        cin >> i >> j;
        count = 0;
        memset(used, false, sizeof(used));
        memset(graph, 0, sizeof(graph));
        int row = 0;
        getchar();

        while (gets(graph[row]) && graph[row][0]) {
            row++;
        }
        dfs(i - 1, j - 1);
        cout << count << endl;
        if (n) {
            cout << endl;
        }
    }

    return 0;
}