Given a matrix where its grid component representing islands and forests, count the number of farmlands.
Intuition
Start from the top left coordinate of the farmland, Use DFS to find the bottom right coordinate of the farmland.
Approach
We define the possible directions as go_right and go_down respectively, we iterate all grids, if it is an grid of the farmland,
then we use DFS to find the bottom right coordinate of the current farmland, and then we mark the farmland as visited and store the coordinates.
Complexity
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
vector<vector<int>> dirs{{0, 1}, {1, 0}};
public:
void dfs(vector<vector<int>>& land, int i, int j, vector<int> &bottom_right) {
land[i][j] = 0;
bool reach_end = true;
for (const auto &dir: dirs) {
int row = i + dir[0], col = j + dir[1];
if (0 <= row && row < land.size() &&
0 <= col && col < land[0].size() &&
land[row][col] == 1) {
reach_end = false;
dfs(land, row, col, bottom_right);
}
}
if (reach_end && bottom_right.empty()) {
bottom_right = vector<int>{i, j};
}
}
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> result;
for (int i = 0; i < land.size(); ++i) {
for (int j = 0; j < land[0].size(); ++j) {
if (land[i][j] == 0) continue;
vector<int> bottom_right;
dfs(land, i, j, bottom_right);
result.push_back(vector<int>{i, j, bottom_right[0], bottom_right[1]});
}
}
return result;
}
};
|