ZeroJudge D165: 草場普查

Z先生為了合理放牧，決定請你為它的牧場進行普查。牧場可以用 N*M 格表示。每個格子上標有一個非負整數，其中用 0 表示穿行在牧場中的道路，而用 1～255 的整數表示這個格子中所種牧草的數量，數字越大，牧草越多。一個種有牧草的格子可以通過「上、下、左、右」四個方向與其它種有牧草的格子形成一個大的「草場」，而一個草場中所有格子標有的整數的和就是這個草場的牧草的蘊藏量。

如：
0 1 0 0
0 0 0 7
8 3 0 9

上圖是一個 3*4 的牧場範例，分成三個草場，它們的蘊藏量分別是 1、11 和 16，最大的牧場牧草蘊藏量是 16。

範例測資

範例輸入範例輸出
EOF 輸入，每組測試資料的第一行有兩個整數 N 和 M ，1 <= N、M <= 100，兩個整數之間用一個空格隔開。以下 N 行，每行有 M 個 0 到 255 的整數，表示這個 N*M 的網絡，同一行中相鄰兩個數字之間用一個空格隔開。對於每組測試數據，輸出兩行。第一行是草場的數量，第二行是最大的草場的牧草蘊藏量。
3 4
0 1 0 0
0 0 0 7
8 3 0 9		3
16
ZeroJudge D165 範例測資

解題思路

使用 BFS 的方式來確認每一塊區域，並且紀錄已經走過的點，已經走過的話就沒有必要再設為新的 BFS 起點了。BFS 可以回傳一個數字，當沒有起點時就回傳這個數字。

範例程式碼－ZeroJudge D165: 草場普查

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

int N, M, farm[500][500] = {}, MAP[500][500] = {}, ans = 0, loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void BFS(const vector<pair<int, int>>start, int count) {
    if (start.size() == 0) {
        ans = max(ans, count);
        return;
    }
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int y = start[i].first, x = start[i].second;
        if (MAP[y][x] != 0) continue;
        MAP[y][x]++;
        count += farm[y][x];
        for (int j = 0; j<4; j++) {
            const int yy = y + loc[j][0], xx = x + loc[j][1];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M && MAP[yy][xx] == 0 && farm[yy][xx] != 0) {
                newStart.push_back(make_pair(yy, xx));
            }
        }
    }
    BFS(newStart, count);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M) {
        ans = 0;
        for (int i = 0; i<N; i++) {
            for (int j = 0; j<M; j++) {
                cin >> farm[i][j];
                MAP[i][j] = 0;
            }
        }
        int land = 0;
        for (int i = 0; i<N; i++) {
            for (int j = 0; j<M; j++) {
                if (farm[i][j] != 0 && MAP[i][j] == 0) {
                    land++;
                    vector<pair<int, int>>start;
                    start.push_back(make_pair(i, j));
                    BFS(start, 0);
                }
            }
        }
        cout << land << "\n" << ans << "\n";
    }
}

//ZeroJudge D165
//Dr. SeanXD
標籤

相關文章

發佈留言