To manage his pasture more efficiently, Mr. Z has asked you to conduct a survey of the pasture. The pasture can be represented as an N * M grid. Each cell in the grid contains a non-negative integer, where 0 represents a road passing through the pasture, and integers from 1 to 255 represent the amount of grass planted in that cell—the larger the number, the more grass is present. A grassy cell can connect with other grassy cells in the “up, down, left, right” directions to form a large “grassland.” The sum of the integers in all the cells within a grassland represents the total grass reserves of that grassland.
For example:
0 1 0 0
0 0 0 7
8 3 0 9
The diagram above is a 3x4 pasture example, divided into three grasslands, with reserves of 1, 11, and 16, respectively. The largest grassland has a total grass reserve of 16.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input. Each test case starts with a line containing two integers, N and M (1 ≤ N, M ≤ 100), separated by a space. The following N lines each contain M integers ranging from 0 to 255, representing the N x M grid. Each integer is separated by a space within the same line. | For each test case, output two lines. The first line should be the number of pastures, and the second line should be the maximum amount of grass stored in any pasture. |
| 3 4 0 1 0 0 0 0 0 7 8 3 0 9 | 3 16 |
Thought Process
Use BFS to identify each region and record the points that have already been visited. If a point has already been visited, it should not be set as a new BFS starting point. BFS can return a number, representing the total amount of grass in the current pasture, which is given when there are no more starting points to process.
Sample Code－ZeroJudge D165: Pasture Census
#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