图论day57|101.孤岛的总面积(卡码网）【逆向思维】 、102.沉没孤岛（卡码网）、103.水流问题(卡码网)【逆向思维】

server/2024/10/17 22:35:07/

图论day57|101.孤岛的总面积(卡码网）【逆向思维】 、102.沉没孤岛（卡码网）、103.水流问题(卡码网）【逆向思维】

    • 101.孤岛的总面积(卡码网)
    • 102.沉没孤岛（卡码网）
    • 103.水流问题(卡码网)

101.孤岛的总面积(卡码网)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1

提示信息

img

在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。

数据范围：

1 <= M, N <= 50。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int count=0;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void bfs(vector<vector<int>> &grid,int x,int y)
{queue<pair<int,int>> que;que.push({x,y});grid[x][y]=0;count++;while(!que.empty()){pair<int,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[1].size())continue;if(grid[nextx][nexty]==1){que.push({nextx,nexty});count++;grid[nextx][nexty]=0;}}}
}int main()
{int n,m;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];for(int i=1;i<=n;i++){if(grid[i][1]==1) bfs(grid,i,1);if(grid[i][m]==1) bfs(grid,i,m);}for(int j=1;j<=m;j++){if(grid[1][j]==1) bfs(grid,1,j);if(grid[n][j]==1) bfs(grid,n,j);}count=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(grid[i][j]==1)bfs(grid,i,j);cout<<count<<endl;}

分析过程如下：
在这里插入图片描述

102.沉没孤岛（卡码网）

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（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

输出示例

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

提示信息

img

将孤岛沉没。

img

数据范围：

1 <= M, N <= 50。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2]={1,0,-1,0,0,1,0,-1};
void bfs(vector<vector<int>> &grid,int x,int y)
{queue<pair<int,int>> que;que.push({x,y});grid[x][y]=0;while(!que.empty()){pair<int,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[1].size())continue;if(grid[nextx][nexty]==1){que.push({nextx,nexty});grid[nextx][nexty]=0;}}}
}int main()
{int n,m;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];vector<vector<int>> grid0=grid;for(int i=1;i<=n;i++){if(grid[i][1]==1) bfs(grid,i,1);if(grid[i][m]==1) bfs(grid,i,m);}for(int j=1;j<=m;j++){if(grid[1][j]==1) bfs(grid,1,j);if(grid[n][j]==1) bfs(grid,n,j);}vector<vector<int>> grid1(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(grid[i][j]==1)grid1[i][j]=0;else if(grid[i][j]==0)grid1[i][j]=1;}vector<vector<int>> grid2(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(grid0[i][j]==1&&grid1[i][j]==1)grid2[i][j]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=m-1;j++){cout<<grid2[i][j]<<" ";}cout<<grid2[i][m]<<endl;}
}

在这里插入图片描述

103.水流问题(卡码网)

题目描述

现有一个 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

提示信息

img

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 100。

1.常规思维

具体代码来自卡哥，时间复杂度是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};// 从 x，y 出发 把可以走的地方都标记上
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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(vector<vector<int>>& grid, int x, int y) {vector<vector<bool>> visited(n, vector<bool>(m, false));// 深搜，将x,y出发 能到的节点都标记上。dfs(grid, visited, x, y);bool isFirst = false;bool isSecond = false;// 以下就是判断x，y出发，是否到达第一组边界和第二组边界// 第一边界的上边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;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];}}// 遍历每一个点，看是否能同时到达第一组边界和第二组边界for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (isResult(grid, i, j)) {cout << i << " " << j << endl;}}}
}

2.逆向思维

时间复杂度为O(n*m)

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(vector<vector<int>> grid,vector<vector<bool>> &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[1].size())continue;if(grid[nextx][nexty]<grid[x][y])continue;dfs(grid,visited,nextx,nexty);}
}int main()
{int n,m;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];vector<vector<bool>> firstVisited(n+1,vector<bool>(m+1,false));vector<vector<bool>> secondVisited(n+1,vector<bool>(m+1,false));for(int i=1;i<=n;i++){dfs(grid,firstVisited,i,1);dfs(grid,secondVisited,i,m);}for(int j=1;j<=m;j++){dfs(grid,firstVisited,1,j);dfs(grid,secondVisited,n,j);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(firstVisited[i][j]&&secondVisited[i][j])cout<<i-1<<" "<<j-1<<endl;
}

在这里插入图片描述


http://www.ppmy.cn/server/131750.html

相关文章

从opencv-python入门opencv--GUI功能之图像和视频操作

从opencv-python入门opencv--GUI功能之图像和视频操作

从opencv-python入门opencv--GUI功能之图像和视频操作 一、文章介绍二、图像的读取显示及保存1、 cv.imread()2、cv.imshow()3、cv.imwrite()4、cv.waitKey()5、cv.destroyAllWindows()6、图像读写存完整示例代码及效果 三、视频读取保存功能1、cv.VideoCapture()&#xff08;1…
阅读更多...
SpringBoot项目错误日志打印不容易注意到的坑

SpringBoot项目错误日志打印不容易注意到的坑

文章目录 一、不要使用e.printStackTrace()二、不要使用log.error(e.getMessage())三、不要在日志打印时进行字符串拼接 先说结论&#xff1a;建议使用log.error(String msg, Throwable t)方式打印错误日志&#xff0c;最好在加上try中的各种参数的信息方便排查 Slf4j public …
阅读更多...
YARN调度原理详解

YARN调度原理详解

YARN&#xff08;Yet Another Resource Negotiator&#xff09;是 Hadoop 集群的资源管理和作业调度框架&#xff0c;它的设计旨在更好地管理和调度 Hadoop 集群中的资源。YARN 解决了传统 Hadoop MapReduce 中资源管理与作业调度紧耦合的问题&#xff0c;使得不同类型的计算任…
阅读更多...
数据中心物理安全的历史和演变

数据中心物理安全的历史和演变

在当今的数字时代&#xff0c;数据中心托管已成为我们互联世界的支柱。这些设施在存储、管理和处理我们日常生活所需的大量信息方面发挥着至关重要的作用。从社交媒体平台和电子商务网站到流媒体服务和云计算&#xff0c;数据中心为我们依赖的数字服务提供支持。 随着企业越来…
阅读更多...
基于FPGA的多路视频缓存

基于FPGA的多路视频缓存

对于多路视频传输的场合&#xff0c;需要正确设置同步。 uifdma_dbuf0 的写通道输出帧同步计数器直接接入 uifdma_dbuf0&#xff0c;uifdma_dbuf1, uifdma_dbuf2, uifdma_dbuf3 的写通道同步计数输入。uifdma_dbuf0 的读通道&#xff0c;延迟 1 帧于 uifdma_dbuf0 的写通道帧计…
阅读更多...
React Native源码学习

React Native源码学习

核心组件 基础组件&#xff1a;View、Text、Image、TextInput、ScrollView&#xff08;性能没有FlatList好&#xff0c;因为它会一次性把子元素渲染出来&#xff09;、StyleSheet交互组件&#xff1a;button列表视图&#xff1a;FlatList&#xff08;优先渲染屏幕上可见的元素&…
阅读更多...
交替最小二乘法（ALS）的工作原理

交替最小二乘法（ALS）的工作原理

假设我们有一个评分矩阵&#xff0c;我们希望通过交替优化用户矩阵和物品矩阵来最小化误差。 假设&#xff1a; 我们有一个评分矩阵 ( R )&#xff0c;它的维度是 ( m \times n )&#xff0c;即 ( m ) 个用户和 ( n ) 个物品&#xff08;比如电影、商品等&#xff09;。矩阵分…
阅读更多...
CSS常用声明（属性）

CSS常用声明（属性）

目录 一、文本 1、字体属性 2、文本修饰 二、图像 1、图像边框样式 2、图像透明度 三、背景 1、background-color&#xff1a;背景颜色 2、background-img&#xff1a;背景图像 3、背景展示效果 4、background-size&#xff1a;背景图大小 5、background-position&…
阅读更多...
最新文章

Copyright @ 2022~2023