随想录 Day 66 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题

2024-06-23 22:12
文章标签 孤岛 随想录 day 66 101 102 103 沉没 总面积 水流 问题

本文主要是介绍随想录 Day 66 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

随想录 Day 66 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题

101. 孤岛的总面积

101. 孤岛的总面积

时间限制：1.000S 空间限制：256MB
题目描述
给定一个由 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

提交 bfs/dfs版本

混用了，这里main函数调用bfs和dfs同效果

# include<iostream>
# include<vector>
# include<queue>
using namespace std;
int count;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
int n, m;
void dfs(vector<vector<int> >& map, int i , int j) {if (map[i][j] == 0) return;count ++;map[i][j] = 0;for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >= 0 && x < n && y>= 0 &&y < m) {dfs(map, x, y);}}
}
void bfs(vector<vector<int> >& map, int i, int j) {if (map[i][j] == 0) return;count ++;map[i][j] = 0;vector<int> now;now.push_back(i);now.push_back(j);queue<vector<int> > que;que.push(now);while(que.size() != 0) {i = que.front()[0];j = que.front()[1];que.pop();for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >= 0 && x< n &&y >= 0 && y < m) {if(map[x][y] == 1) {count ++;map[x][y] = 0;now[0] = x;now[1] = y;que.push(now);}}}}
}
int main() {cin>> n >> m;vector<vector<int> >map(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin>>map[i][j];}}count = 0;for (int j = 0; j < m; j++) {bfs(map, 0, j);bfs(map, n-1, j);}for (int i = 0; i < n; i++) {bfs(map, i, 0);bfs(map, i, m-1);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {dfs(map, i, j);}}cout << count;
}

102. 沉没孤岛

102. 沉没孤岛

时间限制：1.000S 空间限制：256MB
题目描述
给定一个由 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
提示信息

提交 bfs/dfs版本

先遍历所有和边缘相链接的，变成2，从空间上省去了用visitedmap的情况

# include<iostream>
# include<vector>
# include<queue>
using namespace std;
int count;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
int n, m;
void dfs(vector<vector<int> >& map, int i , int j, int changeTo) {if (map[i][j] != 1) return;count ++;map[i][j] = changeTo;for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >= 0 && x < n && y>= 0 &&y < m) {dfs(map, x, y, changeTo);}}
}
int main() {cin>> n >> m;vector<vector<int> >map(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin>>map[i][j];}}count = 0;for (int j = 0; j < m; j++) {dfs(map, 0, j, 2);dfs(map, n-1, j, 2);}for (int i = 0; i < n; i++) {dfs(map, i, 0, 2);dfs(map, i, m-1, 2);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {dfs(map, i, j, 0);}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j] == 2) {map[i][j] = 1;}cout << map[i][j]<< " ";}cout << 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

提交

第一次就直接写出了逆流而上方法,整体逻辑和题解基本没区别

# include <iostream>
# include <vector>
using namespace std;
int dirs[4][2] = {{1, 0},{-1, 0},{0, 1},{0, -1}
};
int n, m;
void dfs(vector<vector<int> > map, vector<vector<int> >& from, int i , int j) {if (from[i][j] == 0) return;from[i][j] = 0;for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >=0 && x < n && y >=0 && y < m) {if (map[x][y] >= map[i][j]) {dfs(map, from, x, y);}}}
}
int main() {cin>> n >> m;vector<vector<int> > map(n, vector<int>(m));vector<vector<int> > formBolderOne(n, vector<int>(m, 1));vector<vector<int> > formBolderTwo(n, vector<int>(m, 1));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin>>map[i][j];}}for (int i = 0; i < n; i++) {dfs(map, formBolderOne, i , 0);dfs(map, formBolderTwo, i , m-1);}for (int j = 0; j < m; j++) {dfs(map, formBolderOne, 0 , j);dfs(map, formBolderTwo, n-1 , j);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (formBolderOne[i][j] == 0 && formBolderTwo[i][j] == 0) {cout << i << " "<<j << endl;}}}
}

104.建造最大岛屿

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

提交

耗费了较多时间，
1：注意输入，要检测
2：与一块儿地多次接壤，会重复计算

# include<iostream>
# include<vector>
# include<unordered_map>
# include<unordered_set>
using namespace std;
int n, m;
int count;
int res;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
void dfs(vector<vector<int> >& map, int i , int j, int changeTo) {if (map[i][j] != 1) return;map[i][j] = changeTo;count ++;for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >=0 && x < n && y >=0 && y < m) {dfs(map, x, y, changeTo);}}
}
int main() {cin >>n >> m;vector<vector<int> > map(n, vector<int>(m, 0));unordered_map<int, int> match;match[0] = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >>map[i][j];}}count= 0;res = 0;int type = 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j] == 1) {type ++;dfs(map, i, j , type);match[type] = count;res = max(count, res);count = 0;}}}unordered_set<int> set;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (map[i][j] == 0) {int temp = 0;for (int k = 0; k < 4; k++) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x >=0 && x < n && y >=0 && y < m) {if (!set.count(map[x][y])) {set.insert(map[x][y]);temp += match[map[x][y]];}}}set.clear();res = max(res, temp + 1);}}}cout<< res;
}

这篇关于随想录 Day 66 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1088421。

相关文章

linux生产者，消费者问题

linux生产者，消费者问题

pthread_cond_wait() ：用于阻塞当前线程，等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径 理论基础 int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
阅读更多...
2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

1.问题产生原因： 1.文件编码不一致：如果文件的编码方式与IDEA设置的编码方式不一致，就会产生乱码。确保文件和IDEA使用相同的编码，通常是UTF-8。2.IDEA设置问题：检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题：如果你在终端或控制台看到乱码，可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案： 1.File -> S
阅读更多...
vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

我是按照网上的vcpkg安装opencv方法进行的（比如这篇：从0开始在visual studio上安装opencv（超详细，针对小白）），但是中间出现了一些别人没有遇到的问题，虽然原因没有找到，但是本人给出一些暂时的解决办法： 问题1： 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64，vcpkg在这条命令后默认下载的也是opencv2:x6
阅读更多...
问题-windows-VPN不正确关闭导致网页打不开

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢？ 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开，我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候，会把ip链接断掉，如果你不正确关掉，ip链接没有断掉，此时你vpn又是没启动的，没有域名解析，所以就打不开网站。 你可以在打不开网页的时候，把vpn打开，你会发现网络又可以登录了。 方法一 注意：方法一虽然方便，但是可能会有
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
vue同页面多路由懒加载-及可能存在问题的解决方式

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图，再解释 图一是多路由页面，图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应，并且图二的路由层在跟图一对应的页面中要加上components层，多一个s结尾，里面的的方法名就是图一路由的name值，里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在
阅读更多...
vue+elementui--$message提示框被dialog遮罩层挡住问题解决

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容，然后接着弹出dialog带遮罩层弹框。那么问题来了，message提示框会默认被dialog遮罩层挡住，现在就是要解决这个问题。 由于都是弹框，问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性，我们可以利用
阅读更多...
Visual Studio中，MSBUild版本问题

Visual Studio中，MSBUild版本问题

假如项目规定了MSBUild版本，那么在安装完Visual Studio后，假如带的MSBUild版本与项目要求的版本不符合要求，那么可以把需要的MSBUild添加到系统中，然后即可使用。步骤如下：            假如项目需要使用V12的MSBUild，而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包，把V12包解压到目录（
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2