Day51

101. 孤島的總面積

思路

從周邊找到陸地然后 通過 dfs或者bfs 將周邊靠陸地且相鄰的陸地都變成海洋，然后再去重新遍歷地圖 統(tǒng)計(jì)此時(shí)還剩下的陸地

代碼

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四個(gè)方向
int count; // 統(tǒng)計(jì)符合題目要求的陸地空格數(shù)量
void dfs(vector<vector<int>>& grid, int x, int y) {grid[x][y] = 0;count++;for (int i = 0; i < 4; i++) { // 向四個(gè)方向遍歷int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超過邊界if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 不符合條件，不繼續(xù)遍歷if (grid[nextx][nexty] == 0) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 從左側(cè)邊，和右側(cè)邊 向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 從上邊和下邊 向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) dfs(grid, i, j);}}cout << count << endl;
}