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

2024-06-23 22:12

本文主要是介绍随想录 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

相关文章

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例

解决Entity Framework中自增主键的问题

《解决EntityFramework中自增主键的问题》:本文主要介绍解决EntityFramework中自增主键的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录Entity Framework中自增主键问题解决办法1解决办法2解决办法3总结Entity Fram