英国男女做那个视频网站,贵州省建设厅二建报名网站,网站建设图片排版,移动互联网应用程序管理情况提示#xff1a;DDU#xff0c;供自己复习使用。欢迎大家前来讨论~ 文章目录 图论part03题目一#xff1a;101.孤岛的总面积解题思路DFS**BFS** 题目二#xff1a;102. 沉没孤岛解题思路 题目三#xff1a;103. 水流问题解题思路优化 题目四#xff1a;104.建造最大岛屿…提示DDU供自己复习使用。欢迎大家前来讨论~ 文章目录 图论part03题目一101.孤岛的总面积解题思路DFS**BFS** 题目二102. 沉没孤岛解题思路 题目三103. 水流问题解题思路优化 题目四104.建造最大岛屿解题思路优化思路 总结 图论part03
题目一101.孤岛的总面积
101. 孤岛的总面积 (kamacoder.com)
解题思路
本题使用dfsbfs并查集都是可以的。
本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。
如图在遍历地图周围四个边靠地图四边的陆地都为绿色 在遇到地图周边陆地的时候将1都变为0此时地图为这样 然后我们再去遍历这个地图遇到有陆地的地方去采用深搜或者广搜边统计所有陆地。
DFS
采用深度优先搜索的代码如下
#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;
}BFS
采用广度优先搜索的代码如下
#include iostream
#include vector
#include queue
using namespace std;
int count 0;
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vectorvectorint grid, int x, int y) {queuepairint, int que;que.push({x, y});grid[x][y] 0; // 只要加入队列立刻标记count;while(!que.empty()) {pairint ,int cur que.front(); que.pop();int curx cur.first;int cury cur.second;for (int i 0; i 4; i) {int nextx curx dir[i][0];int nexty cury dir[i][1];if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 越界了直接跳过if (grid[nextx][nexty] 1) {que.push({nextx, nexty});count;grid[nextx][nexty] 0; // 只要加入队列立刻标记}}}
}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) bfs(grid, i, 0);if (grid[i][m - 1] 1) bfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j 0; j m; j) {if (grid[0][j] 1) bfs(grid, 0, j);if (grid[n - 1][j] 1) bfs(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) bfs(grid, i, j);}}cout count endl;
}题目二102. 沉没孤岛
102. 沉没孤岛 (kamacoder.com)
解题思路
标记边缘陆地从地图的边缘开始将所有边缘的陆地1标记为特殊值2。转换中间陆地遍历整个地图将未标记的陆地1转换为水域0。恢复边缘标记将特殊标记2恢复为陆地1。 整体C代码如下以下使用dfs实现其实遍历方式dfsbfs都是可以的。
#include iostream
#include vector
using namespace std;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 2;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 || grid[nextx][nexty] 2) 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);}// 步骤二、步骤三for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 1) grid[i][j] 0;if (grid[i][j] 2) grid[i][j] 1;}}for (int i 0; i n; i) {for (int j 0; j m; j) {cout grid[i][j] ;}cout endl;}
}题目三103. 水流问题
103. 水流问题 (kamacoder.com)
解题思路
想象你有一块高低不平的地形这块地形是一个由很多小格子组成的矩形每个小格子都有一个高度值。现在下了一场雨雨水会从高处流向低处但是雨水只能流向四个方向上、下、左、右而且只能流向比它低或者一样高的地方。
现在我们要找出那些雨水可以流到地形边缘的格子。地形的边缘分为两组第一组是地形的左边界和上边界第二组是右边界和下边界。
任务就是找出所有那些雨水可以流到这两组边界的格子并输出这些格子的坐标。
就是找出那些雨水可以流到地形边缘的格子并告诉你这些格子在哪里。
输入你会得到一个矩形矩阵矩阵的大小由两个数字 N 和 M 决定N 表示行数M 表示列数。矩阵中的每个数字代表一个小格子的高度。输出你需要找出所有那些雨水可以流到地形的左边界或上边界第一组边界的格子以及所有雨水可以流到地形的右边界或下边界第二组边界的格子。然后你需要输出这些格子的坐标。
一个比较直白的想法其实就是 遍历每个点然后看这个点 能不能同时到达第一组边界和第二组边界。
至于遍历方式可以用dfs也可以用bfs以下用dfs来举例。
#include iostream
#include vector
using namespace std;
int n, m;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};// 从 xy 出发 把可以走的地方都标记上
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue;if (grid[x][y] grid[nextx][nexty]) continue; // 高度不合适dfs (grid, visited, nextx, nexty);}return;
}
bool isResult(vectorvectorint grid, int x, int y) {vectorvectorbool visited(n, vectorbool(m, false));// 深搜将x,y出发 能到的节点都标记上。dfs(grid, visited, x, y);bool isFirst false;bool isSecond false;// 以下就是判断xy出发是否到达第一组边界和第二组边界// 第一边界的上边for (int j 0; j m; j) {if (visited[0][j]) {isFirst true;break;}}// 第一边界的左边for (int i 0; i n; i) {if (visited[i][0]) {isFirst true;break;}}// 第二边界右边for (int j 0; j m; j) {if (visited[n - 1][j]) {isSecond true;break;}}// 第二边界下边for (int i 0; i n; i) {if (visited[i][m - 1]) {isSecond true;break;}}if (isFirst isSecond) return true;return false;
}int main() {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) {for (int j 0; j m; j) {if (isResult(grid, i, j)) {cout i j endl;}}}
}直接对每个单元格进行深度优先搜索DFS会导致非常高的时间复杂度尤其是在矩阵较大的情况下。这种直接的DFS方法在最坏情况下的时间复杂度是 O ( m 2 × n 2 ) O(m^2×n^2) O(m2×n2)这对于大型矩阵来说是不可行的。
优化
那么我们可以 反过来想从第一组边界上的节点 逆流而上将遍历过的节点都标记上。
同样从第二组边界的边上节点 逆流而上将遍历过的节点也标记上。
然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
从第一组边界边上节点出发如图 从第二组边界上节点出发如图 按照这样的逻辑就可以写出如下遍历代码详细注释
#include iostream
#include vector
using namespace std;
int n, m;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue;if (grid[x][y] grid[nextx][nexty]) continue; // 注意这里是从低向高遍历dfs (grid, visited, nextx, nexty);}return;
}int main() {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];}}// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorbool firstBorder(n, vectorbool(m, false));// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorbool secondBorder(n, vectorbool(m, false));// 从最上和最下行的节点出发向高处遍历for (int i 0; i n; i) {dfs (grid, firstBorder, i, 0); // 遍历最左列接触第一组边界dfs (grid, secondBorder, i, m - 1); // 遍历最右列接触第二组边界}// 从最左和最右列的节点出发向高处遍历for (int j 0; j m; j) {dfs (grid, firstBorder, 0, j); // 遍历最上行接触第一组边界dfs (grid, secondBorder, n - 1, j); // 遍历最下行接触第二组边界}for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果这个节点从第一组边界和第二组边界出发都遍历过就是结果if (firstBorder[i][j] secondBorder[i][j]) cout i j endl;;}}}本题整体的时间复杂度其实是 2 ∗ n ∗ m n ∗ m 2 * n * m n * m 2∗n∗mn∗m 所以最终时间复杂度为 O( n ∗ m n * m n∗m) 。
空间复杂度为O(n * m) 。开了几个 n * m 的数组。
题目四104.建造最大岛屿
104. 建造最大岛屿 (kamacoder.com)
解题思路
暴力想法尝试将地图上的每个水域0变成陆地1然后计算这种情况下的最大岛屿面积。计算最大面积通过深度优先搜索DFS或广度优先搜索BFS遍历地图标记岛屿计算面积。这一步的时间复杂度大约是 O( n 2 n^2 n2)因为需要遍历地图上的每个单元格。整体时间复杂度由于地图上有 n2 个单元格每个单元格改变状态后都需要重新计算最大岛屿面积所以整体时间复杂度是 O( n 4 n^4 n4)。
优化思路 记录岛屿面积首先遍历地图一次使用深度优先搜索DFS找出所有的岛屿并记录每个岛屿的面积。这一步可以给每个岛屿一个唯一的编号并使用一个字典或map来存储岛屿编号和对应的面积。 计算最大面积然后再次遍历地图中的水域0对于每个水域单元格计算它变成陆地1后与它相邻的岛屿面积总和。这样对于每个水域单元格你都可以得到一个“潜在的最大面积”即如果这个水域变成陆地与它相邻的所有岛屿合并后的总面积。
通过这两步你可以找到将任意一个水域单元格变成陆地后能够得到的最大岛屿面积。这种方法避免了重复计算提高了效率。
拿如下地图的岛屿情况来举例 1为陆地 第一步则遍历题目并将岛屿到编号和面积上的统计过程如图所示 本过程代码如下
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] 0) return; // 终止条件访问过的节点 或者 遇到海水visited[x][y] true; // 标记访问过grid[x][y] mark; // 给陆地标记新标签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; // 越界了直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int largestIsland(vectorvectorint grid) {int n grid.size(), m grid[0].size();vectorvectorbool visited vectorvectorbool(n, vectorbool(m, false)); // 标记访问过的点unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1) {count 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}
}这个过程时间复杂度 n * n 。可能有录友想分明是两个for循环下面套这一个dfs时间复杂度怎么回事 n * n呢
其实大家可以仔细看一下代码n * n这个方格地图中每个节点我们就遍历一次并不会重复遍历。
第二步过程如图所示 也就是遍历每一个0的方格并统计其相邻岛屿面积最后取一个最大值。
这个过程的时间复杂度也为 n * n。
所以整个解法的时间复杂度为 n * n n * n 也就是 n 2 n^2 n2。
当然这里还有一个优化的点就是 可以不用 visited数组因为有mark来标记所以遍历过的grid[i][j]是不等于1的。
代码如下
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vectorvectorint grid, int x, int y, int mark) {if (grid[x][y] ! 1 || grid[x][y] 0) return; // 终止条件访问过的节点 或者 遇到海水grid[x][y] mark; // 给陆地标记新标签count;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue; // 越界了直接跳过dfs(grid, nextx, nexty, mark);}
}int main() {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];}}unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (grid[i][j] 1) {count 0;dfs(grid, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}不过为了让各个变量各司其事代码清晰一些完整代码还是使用visited数组来标记。
最后整体代码如下
#include iostream
#include vector
#include unordered_set
#include unordered_map
using namespace std;
int n, m;
int count;int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] 0) return; // 终止条件访问过的节点 或者 遇到海水visited[x][y] true; // 标记访问过grid[x][y] mark; // 给陆地标记新标签count;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue; // 越界了直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int main() {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];}}vectorvectorbool visited(n, vectorbool(m, false)); // 标记访问过的点unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1) {count 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}if (isAllGrid) {cout n * m endl; // 如果都是陆地返回全面积return 0; // 结束程序}// 以下逻辑是根据添加陆地的位置计算周边岛屿面积之和int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记访问过的岛屿for (int i 0; i n; i) {for (int j 0; j m; j) {count 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时清空if (grid[i][j] 0) {for (int k 0; k 4; k) {int neari i dir[k][1]; // 计算相邻坐标int nearj j dir[k][0];if (neari 0 || neari n || nearj 0 || nearj m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result max(result, count);}}cout result endl;}总结
坚持