云服务器开网站,企业公司简介,文学网站怎样建设,做搜狗网站排名软Day51
101. 孤岛的总面积
思路
从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋#xff0c;然后再去重新遍历地图 统计此时还剩下的陆地
代码
#include iostream
#include vector
using namespace std;
int dir[4][2] {-1, 0, …Day51
101. 孤岛的总面积
思路
从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地
代码
#include iostream
#include vector
using namespace std;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 0;count;for (int i 0; i 4; i) { // 向四个方向遍历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;// 不符合条件不继续遍历if (grid[nextx][nexty] 0) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}// 从左侧边和右侧边 向中间遍历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;
}
