wordpress多站点文章调用,淘宝客网站需要多大主机,php做的网站 订单系统,网站开发实例图论理论基础与岛屿问题 图论理论基础深度搜索#xff08;dfs#xff09;广度搜索#xff08;bfs#xff09;岛屿问题概述 岛屿数量岛屿数量-深搜版岛屿数量-广搜版 岛屿的最大面积孤岛的总面积沉没孤岛建造最大人工岛水流问题岛屿的周长 图论理论基础
这里仅对图论相关核… 图论理论基础与岛屿问题 图论理论基础深度搜索dfs广度搜索bfs岛屿问题概述 岛屿数量岛屿数量-深搜版岛屿数量-广搜版 岛屿的最大面积孤岛的总面积沉没孤岛建造最大人工岛水流问题岛屿的周长 图论理论基础
这里仅对图论相关核心概念做整理总结归纳具体详细相关概念请参考代码随想录上的整理总结
图论理论基础深度优先搜索理论基础所有可达路径-dfs实战广度优先搜索理论基础
图的遍历方式基本是两大类
深度优先搜索dfs广度优先搜索bfs
dfs和bfs的区别
dfs是沿一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯二叉树的前中后序遍历、以及回溯算法就是dfs过程。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程二叉树的层序遍历就是bfs的过程。
深度搜索dfs dfs搜索过程是沿着一个方向搜不到黄河不回头举个例子如图是一个无向图我们要搜索从节点1到节点6的所有路径那么dfs搜索的第一条路径是这样的假设第一次延默认方向就找到了节点6 此时我们找到了节点6遇到黄河了是不是应该回头了那么应该再去搜索其他方向了如下图: 路径2撤销了改变了方向走路径3红色线 接着也找到终点6。 那么撤销路径2改为路径3在dfs中其实就是回溯的过程这一点很重要)
又找到了一条从节点1到节点6的路径又到黄河了此时再回头下图图四中路径4撤销回溯改为路径5 又找到了一条从节点1到节点6的路径又到黄河了此时再回头如下图路径6撤销回溯的过程改为路径7路径8 和 路径7路径9 结果发现死路一条都走到了自己走过的节点 那么节点2所连接路径和节点3所链接的路径 都走过了撤销路径只能向上回退去选择撤销当初节点4的选择也就是撤销路径5改为路径10 。 如下图 上图演示中其实并没有把 所有的 从节点1 到节点6的dfs深度优先搜索的过程都画出来那样太冗余了但 已经把dfs 关键的地方都涉及到了关键就两点
搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程。
代码框架
vectorvectorint result; // 保存符合条件的所有路径
vectorint path; // 起点到终点的路径
void dfs(图目前搜索的节点)
{if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}其实很多dfs写法没有写终止条件其实终止条件写在了 下面dfs递归的逻辑里了也就是不符合条件直接不会向下递归 到这里对回溯算法会有更深刻的理解路径2 已经走到了 目的地节点6那么 路径2 是如何撤销然后改为 路径3呢 其实这就是 回溯的过程撤销路径2走换下一个方向 广度搜索bfs
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发以起始点为中心一圈一圈进行搜索一旦遇到终点记录之前走过的节点就是一条最短路。当然也有一些问题是广搜 和 深搜都可以解决的例如岛屿问题这类问题的特征就是不涉及具体的遍历方式只要能把相邻且相同属性的节点标记上就行。
广搜的过程 BFS是一圈一圈的搜索过程我们用一个方格地图假如每次搜索的方向为 上下左右不包含斜上方那么给出一个start起始位置那么BFS就是从四个方向走出第一步 如果加上一个end终止位置那么使用BFS的搜索过程如图所示 正是因为BFS一圈一圈的遍历方式所以一旦遇到终止点那么一定是一条最短路径。
而且地图还可以有障碍如图所示 代码框架
其实我们仅仅需要一个容器能保存我们要遍历过的元素就可以那么用队列还是用栈甚至用数组都是可以的。用队列的话就是保证每一圈都是一个方向去转例如统一顺时针或者逆时针。因为队列是先进先出加入元素和弹出元素的顺序是没有改变的。如果用栈的话就是第一圈顺时针遍历第二圈逆时针遍历第三圈有顺时针遍历。由于各种教程习惯用队列较多这里我也使用队列来实现只是记录并不是非要用队列用栈也可以。
广搜代码模板该模板针对的就是上面的四方格的地图
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y)
{queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点// 开始遍历队列里的元素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 (!visited[nextx][nexty]) { que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] true; // 只要加入队列立刻标记避免重复访问}}}
}务必理解上述代码在下述的岛屿问题解决相邻的问题上也将用到相似的思路与代码。
岛屿问题概述
在图论中有一类基础问题即是岛屿问题其中有关岛屿问题的通识描述如下
给定一个由 1陆地 和 0水 组成的矩阵岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域你可以假设矩阵外均被水包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。后续 N 行每行包含 M 个数字数字为 1 或者 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1岛屿数量
卡码网题目链接ACM模式
岛屿数量-深搜版
遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过 这样计数器就是最终岛屿的数量。
程序实现版本一
#include iostream
#include vectorusing namespace std;//四个方向
int dir[4][2] {0,1,1,0,-1,0,0,-1};
void dfs(const vectorvectorint grid, vectorvectorbool visited, int x, int y)
{// 开始想当前节点的四个方向左右上下去遍历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(!visited[nextx][nexty] grid[nextx][nexty] 1){// 标记访问过visited[nextx][nexty] true;// 深度搜索该陆地四周相邻的陆地dfs(grid, visited, nextx, nexty);}}
}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];}// 标记该节点是否被访问过vectorvectorbool visited(n,vectorbool(m,false));int result 0; // 记录岛屿数量for(int i 0; i n; i){for(int j 0; j m; j){if(!visited[i][j] grid[i][j] 1){visited[i][j] true; // 标记该节点已被访问result; // 遇到没访问过的陆地1dfs(grid,visited,i,j); // 将与其连接的陆地都标记上 true}}}cout result endl;return 0;
}为什么 以上代码中的dfs函数没有终止条件呢其实终止条件 就写在了 调用dfs的地方如果遇到不合法的方向直接不会去调用dfs。
当然也可以这么写版本二
// 版本二
#include iostream
#include vector
using namespace std;
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vectorvectorint grid, vectorvectorbool visited, int x, int y)
{// 终止条件访问过的节点 或者 遇到海水if (visited[x][y] || grid[x][y] 0) 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 grid.size() || nexty 0 || nexty grid[0].size()) continue; // 越界了直接跳过//不做判断 直接递归dfs(grid, visited, nextx, nexty);}
}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];}}vectorvectorbool visited(n, vectorbool(m, false));int result 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (!visited[i][j] grid[i][j] 1) {// 遇到没访问过的陆地1result; // 不先标记 直接递归dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout result endl;
}版本一的写法是 下一个节点是否能合法已经判断完了传进dfs函数的就是合法节点。版本二的写法是 不管节点是否合法上来就dfs然后在终止条件的地方进行判断不合法再 return。理论上来讲版本一的效率更高一些因为避免了 没有意义的递归调用在调用dfs之前就做合法性判断。 就个人而言版本一比版本二逻辑更清晰更易于个人理解因此后续都使用版本一的写法。其实本题是 dfsbfs 模板题所以需要注重更多的细节问题更有利于后面对程序的修改与扩展。
岛屿数量-广搜版 当然本题也是 bfs的一个模板题也可以使用bfs来解决即先搜索一个节点周围与其相邻的所有陆地 这里有一个广搜中的重要细节只要加入队列就代表走过就需要标记而不是从队列拿出来的时候再去标记走过。 如果从队列拿出节点再去标记这个节点走过就会发生下图所示的结果会导致很多节点重复加入队列。 超时写法 从队列中取出节点再标记注意代码注释的地方
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que;que.push({x, y});while(!que.empty()) {pairint ,int cur que.front(); que.pop();int curx cur.first;int cury cur.second;visited[curx][cury] true; // 从队列中取出在标记走过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 (!visited[nextx][nexty] grid[nextx][nexty] 1) {que.push({nextx, nexty});}}}
}加入队列 就代表走过立刻标记正确写法 注意代码注释的地方
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que;que.push({x, y});// 只要加入队列立刻标记visited[x][y] true; 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 (!visited[nextx][nexty] grid[nextx][nexty] 1) {que.push({nextx, nexty});// 只要加入队列立刻标记visited[nextx][nexty] true; }}}
}以上两个版本其实其实只有细微区别就是 visited[x][y] true; 放在的地方这取决于我们对 代码中队列的定义队列中的节点就表示已经走过的节点。 所以只要加入队列立即标记该节点走过。
完整广搜代码实现
#include iostream
#include vector
#include queueusing namespace std;int dir[4][2] {1,0,0,1,-1,0,0,-1};
void bfs(vectorvectorint grid, vectorvectorbool visited, int x, int y)
{queuepairint, int que;que.push({x,y});// 只要加入队列立刻标记visited[x][y] true;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(!visited[nextx][nexty] grid[nextx][nexty] 1){que.push({nextx,nexty});visited[nextx][nexty] true;}}}
}int main()
{int n,m;cin n m;vectorvectorint grid(n,vectorint(m));vectorvectorbool visited(n,vectorbool(m,false));for(int i 0; i n; i){for(int j 0; j m; j){cin grid[i][j];}}int result 0;for(int i 0; i n; i){for(int j 0; j m; j){if(!visited[i][j] grid[i][j] 1){// 遇到没访问过的陆地1result;// 将与其链接的陆地都标记上 truebfs(grid,visited,i,j);}}}cout result endl;return 0;
}岛屿的最大面积
卡码网题目链接ACM模式
本题也是 dfs bfs基础类题目就是搜索每个岛屿上 1 的数量然后取一个最大的。根据上述两种版本的写法这里 dfs只处理下一个节点即在主函数遇到岛屿就计数为1dfs处理接下来的相邻陆地
程序实现(dfs)
#include iostream
#include vectorusing namespace std;int area; //当前面积
int dir[4][2] {1,0,0,1,-1,0,0,-1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y)
{//遍历四周的岛屿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(!visited[nextx][nexty] grid[nextx][nexty] 1){visited[nextx][nexty] true;area; //面积 1//深度搜索下一个的相连的岛屿dfs(grid,visited,nextx,nexty);}}
}int main()
{int n,m;int result 0;cin n m;vectorvectorint grid(n,vectorint(m));vectorvectorbool visited(n,vectorbool(m,false));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(!visited[i][j] grid[i][j] 1){visited[i][j] true;area 1;dfs(grid,visited,i,j); //标记相连的陆地为trueresult max(result,area); //记录最大的陆地面积}}}cout result endl;
}孤岛的总面积
卡码网101. 孤岛的总面积 本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。
如图在遍历地图周围四个边靠地图四边的陆地都为绿色 在遇到地图周边陆地的时候将1都变为0此时地图为这样 然后我们再去遍历这个地图遇到有陆地的地方去采用深搜或者广搜边统计所有陆地。
程序实现dfs
#include iostream
#include vectorusing namespace std;// 本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs
//将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。// 将相连的岛屿全部变成海洋
int dir[4][2] {1,0,0,1,-1,0,0,-1};
int cnt 0;
void dfs(vectorvectorint grid, int x, int y)
{//标记变成海洋grid[x][y] 0;//用于第二次求孤岛的面积使用 面积cnt;// 遍历四周是否有陆地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] 1)dfs(grid,nextx,nexty);}return;
}int main()
{int n;int m;cin n m;// 输入图vectorvectorint grid(n,vectorint(m));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);}cnt 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 cnt endl;
}沉没孤岛
卡码网题目链接ACM模式
本题和上述孤岛的总面积正好反过来了上述是求孤岛的面积而这题是将孤岛的1改为0那么两题在思路上也是差不多的思路依然是从地图周边出发将周边空格相邻的陆地都做上标记改为2然后再遍历一遍地图遇到 陆地 且没做过标记的那么都是地图中间的 陆地 全部改成水域就行。
步骤一 深搜或者广搜将地图周边的 1 陆地全部改成 2 特殊标记
步骤二 将水域中间 1 陆地全部改成 水域0
步骤三 将之前标记的 2 改为 1 陆地 程序实现dfs:
#include iostream
#include vectorusing namespace std;int dir[4][2] {1,0,0,1,-1,0,0,-1};
//将靠近地图周边的岛屿全部变成 2
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] 1)dfs(grid,nextx,nexty);}
}int main()
{int n, m;cin n m;vectorvectorint grid(n,vectorint(m));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);} // cout temp: endl;
// for(int i 0; i n;i)
// {
// for(int j 0; j m; j)
// {
// cout grid[i][j] ;
// }
// cout endl;
// }//步骤二 三 周围陆地变成1 孤岛陆地为0for(int i 0; i n; i){for(int j 0; j m; j){//两个顺序不能换 否则全为0if(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;}
}建造最大人工岛
卡码网题目链接ACM模式 给定一个由 1陆地和 0水组成的矩阵最多可以将矩阵中的一格水变为一块陆地在执行了此操作之后矩阵中最大的岛屿面积是多少
案例 输入陆地与海洋信息如下 对于上面的案例有两个位置可将 0 变成 1使得岛屿的面积最大即 6。 思路
本题的一个暴力想法应该是遍历地图尝试 将每一个 0 改成1然后去搜索地图中的最大的岛屿面积。计算地图的最大面积遍历地图 深搜岛屿时间复杂度为 n ∗ n n * n n∗n。每改变一个0的方格都需要重新计算一个地图的最大面积所以 整体时间复杂度为 n 4 n^4 n4
优化思路
其实每次深搜遍历计算最大岛屿面积我们都做了很多重复的工作只要用一次深搜把每个岛屿的面积记录下来就好。
第一步 一次遍历地图得出各个岛屿的面积并做编号记录。可以使用map记录key为岛屿编号value为岛屿面积
第二步 再遍历地图遍历0的方格因为要将0变成1并统计该1由0变成的1周边岛屿面积将其相邻面积相加在一起遍历所有 0 之后就可以得出 选一个0变成1 之后的最大面积。
拿如下地图的岛屿情况来举例 1为陆地 第一步 遍历陆地并将岛屿到编号和面积上的统计过程如图所示 统计每一块岛屿的面积并将岛屿面积存入对应的编号map中保存核心代码如下
int area 0; // 统计当前遍历岛屿的面积
int dir[4][2] {1,0,0,1,-1,0,0,-1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int landIdx)
{// 给陆地标记新标签grid[x][y] landIdx;//四个方向都会递归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(!visited[nextx][nexty] grid[nextx][nexty] 1){area;visited[nextx][nexty] true;dfs(grid, visited, nextx, nexty, landIdx);}}
}unordered_mapint, int landArea;
int landIdx 2; //标记岛屿的编号
for(int i 0;i n; i)
{for(int j 0; j m; j){//遍历到新的岛屿 计算每个新陆地形成的岛屿面积if(!visited[i][j] grid[i][j] 1){area 1; // 重新计算一块新的岛屿面积visited[i][j] true;// 将与其连接的陆地都标记上 true 同时给每个岛屿编个号 landIdxdfs(grid, visited, i, j, landIdx); landArea[landIdx] area; // 标记每一块编号为 landIdx 的面积为 area}}
}第二步 遇到海洋将0变成1后看能形成的最大岛屿的面积遍历海洋周围一圈是否有岛屿有则拼接岛屿 这里要注意几个细节
特殊情况 n * m 的网格全部为陆地在海洋周围找到陆地后拼接岛屿完成后需要对该岛屿进行标记否则可能重复拼接周围的同一块岛屿
拼接岛屿核心代码如下
int result 0; // 记录最后结果
unordered_setint visitedGrid; // 标记访问过的岛屿
for(int i 0; i n; i)
{for(int j 0; j m; j){area 1; // 记录连接之后的岛屿面积visitedGrid.clear(); // 每次使用时清空//访问到海洋了 //计算这个海洋节点变成陆地后拼接周围四个方向岛屿的面积if(grid[i][j] 0){for(int k 0; k 4; k){// 计算周围的相邻坐标int nexti i dir[k][0];int nextj j dir[k][1];//越界if(nexti 0 || nexti grid.size() || nextj 0 || nextj grid[0].size())continue; // 添加过的岛屿不要重复添加if(visitedGrid.count(grid[nexti][nextj])) continue; //周围遇到新的陆地if(grid[nexti][nextj] 0){area landArea[grid[nexti][nextj]]; // 拼接面积visitedGrid.insert(grid[nexti][nextj]); // 标记该岛屿已经添加过} }//cout area endl;result max(result,area);}}
}完整代码实现如下
#include iostream
#include vector
#include unordered_map
#include unordered_setusing namespace std;int area 0; // 统计当前遍历岛屿的面积
int dir[4][2] {1,0,0,1,-1,0,0,-1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int landIdx)
{// 给陆地标记新标签grid[x][y] landIdx;//四个方向都会递归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(!visited[nextx][nexty] grid[nextx][nexty] 1){area;visited[nextx][nexty] true;dfs(grid, visited, nextx, nexty, landIdx);}}
}int main()
{int n, m;cin n m;int isAllLand true; //记录是否全部为陆地vectorvectorint grid(n, vectorint(m));vectorvectorbool visited(n, vectorbool(m, false));for(int i 0;i n; i){for(int j 0; j m; j){cin grid[i][j];}}unordered_mapint, int landArea;int landIdx 2; //标记岛屿的编号for(int i 0;i n; i){for(int j 0; j m; j){if(grid[i][j] 0)isAllLand false; //有海洋//遍历到新的岛屿 计算每个新陆地形成的岛屿面积if(!visited[i][j] grid[i][j] 1){area 1;visited[i][j] true;// 将与其连接的陆地都标记上 true 同时给每个岛屿编个号 landIdxdfs(grid, visited, i, j, landIdx); landArea[landIdx] area; // 标记每一块编号为 landIdx 的面积为 area}}}// 全是陆地 不用建造了if(isAllLand true){cout n * m endl;return 0;}// cout area: endl;
// for(int i 2; i landIdx; i)
// {
// cout landArea[i] endl;
// }
//
// cout landIdx: endl;
// for(int i 0; i n; i){
// for(int j 0; j m; j){
// cout grid[i][j] ;
// }
// cout endl;
// }
// int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记访问过的岛屿for(int i 0; i n; i){for(int j 0; j m; j){area 1; // 记录连接之后的岛屿面积visitedGrid.clear(); // 每次使用时清空//访问到海洋了 //计算这个海洋节点变成陆地后拼接周围四个方向岛屿的面积if(grid[i][j] 0){for(int k 0; k 4; k){// 计算周围的相邻坐标int nexti i dir[k][0];int nextj j dir[k][1];//越界if(nexti 0 || nexti grid.size() || nextj 0 || nextj grid[0].size())continue; // 添加过的岛屿不要重复添加if(visitedGrid.count(grid[nexti][nextj])) continue; //周围遇到新的陆地if(grid[nexti][nextj] 0){area landArea[grid[nexti][nextj]]; // 拼接面积visitedGrid.insert(grid[nexti][nextj]); // 标记该岛屿已经添加过} }//cout area endl;result max(result,area);}}}cout result endl;
}水流问题
卡码网题目链接ACM模式
题目描述 现有一个 N × M 的矩阵每个单元格包含一个数值这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界而矩阵的右边界和下边界被视为第二组边界。 矩阵模拟了一个地形当雨水落在上面时水会根据地形的倾斜向低处流动但只能从较高或等高的地点流向较低或等高并且相邻上下左右方向的地点。我们的目标是确定那些单元格从这些单元格出发的水可以达到第一组边界和第二组边界。
输入描述
第一行包含两个整数 N 和 M分别表示矩阵的行数和列数。后续 N 行每行包含 M 个整数表示矩阵中的每个单元格的高度。
输出描述 输出共有多行每行输出两个整数用一个空格隔开表示可达第一组边界和第二组边界的单元格的坐标输出顺序任意。
输入示例
5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1输出示例
0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1提示信息 图中的蓝色方块上的雨水既能流向第一组边界也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。
思路
一个比较直白的想法其实就是 遍历每个点然后看这个点 能不能同时到达第一组边界和第二组边界。遍历每一个节点时间复杂度是 m ∗ n m * n m∗n遍历每一个节点的时候都要做深搜深搜的时间复杂度是 m ∗ n m * n m∗n那么整体时间复杂度 就是 O ( m 2 ∗ n 2 ) O(m^2 * n^2) O(m2∗n2)这是一个四次方的时间复杂度显然时间复杂度超时。那么我们可以 反过来想从第一组边界上的节点 逆流而上将遍历过的节点都标记上。同样从第二组边界的边上节点 逆流而上将遍历过的节点也标记上。然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
从第一组边界边上节点出发如图 从第二组边界上节点出发如图 #include iostream
#include vectorusing 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 grid.size() || nexty 0 || nexty grid[0].size())continue;/// 注意这里是逆向流水if(grid[x][y] grid[nextx][nexty])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;}}
}岛屿的周长
卡码网题目链接ACM模式
在矩阵中恰好拥有一个岛屿假设组成岛屿的陆地边长都为 1请计算岛屿的周长。岛屿内部没有水域。
输出描述 输出一个整数表示岛屿的周长。
输出示例 14
提示信息 思路 岛屿问题最容易让人想到BFS或者DFS但本题确实还用不上。 为了避免惯性思维所以这道题。 遍历每一个空格遇到岛屿则计算其上下左右的空格情况。 如果该陆地上下左右的空格是有水域则说明是一条边如图 如果该陆地上下左右的空格出界了则说明是一条边如图
程序实现
#include iostream
#include vectorusing namespace std;int main()
{int n, m;cin n m;int dir[4][2] {1,0,0,1,-1,0,0,-1}; vectorvectorint grid(n, vectorint(m));for(int i 0; i n; i){for(int j 0; j m; j){cin grid[i][j];}}int res 0;for(int i 0; i n; i){for(int j 0; j m; j){// 遇到陆地if(grid[i][j] 1){//计算周围节点坐标for(int k 0; k 4; k){int nexti i dir[k][0];int nextj j dir[k][1];if( nexti 0 || nexti n || // 越界nextj 0 || nextj m || // 越界grid[nexti][nextj] 0 // 水域){res;}}}}}cout res endl;return 0;
}
