当前位置:网站首页>934.最短的桥(广度优先搜索)
934.最短的桥(广度优先搜索)
2022-07-30 05:38:00 【Linke66】
解题思路
方法1:暴力法
使用深度优先搜索,讲两个岛屿的坐标存储到两个数组中,然后用两个for遍历数组,找到最小置。
很暴力,时间和空间复杂度也很高。
class Solution {
public:
int shortestBridge(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<bool>>visited(m,vector<bool>(n,false));
vector<vector<int>>island1_axis,island2_axis;
int whichIsland=1;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(!visited[i][j]&&grid[i][j]==1){
if(whichIsland==1){
++whichIsland;
dfs(grid,visited,island1_axis,i,j);
continue;
}
if(whichIsland==2){
++whichIsland;
dfs(grid,visited,island2_axis,i,j);
}
}
}
}
int min_cnt=INT_MAX;
int cnt;
for(auto &axis1:island1_axis){
int x1=axis1[0],y1=axis1[1];
for(auto &axis2:island2_axis){
int x2=axis2[0],y2=axis2[1];
cnt=abs(x1-x2)+abs(y1-y2)-1;
if(cnt<min_cnt) min_cnt=cnt;
}
}
return min_cnt;
}
void dfs(const vector<vector<int>> &grid,vector<vector<bool>> &visited,
vector<vector<int>> &axis,int x,int y)
{
if(x>=0&&x<grid.size()&&y>=0&&y<grid[0].size()
&&!visited[x][y]&&grid[x][y]==1){
visited[x][y]=true;
axis.push_back({
x,y});
dfs(grid,visited,axis,x-1,y);
dfs(grid,visited,axis,x+1,y);
dfs(grid,visited,axis,x,y-1);
dfs(grid,visited,axis,x,y+1);
}
}
};
法2:广度优先搜索
处理最短路径问题,使用广度优先搜索方法。
这个方法是看答案的,感觉很巧妙,以前没有想过这种方法,在此记录一下。
先通过深度优先搜索其中一个岛屿,并且将数字变为2,与另一座岛屿区分;然后再通过广度优先搜索,一层一层架桥,直到遇到另一座岛。
class Solution {
vector<int>direction{
-1,0,1,0,-1};
public:
int shortestBridge(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
queue<pair<int,int>>points;
//dfs寻找第一个岛屿,并把1全部赋值为2
bool flipped=false;
for(int i=0;i<m;++i){
if(flipped) break;
for(int j=0;j<n;++j){
if(grid[i][j]==1){
dfs(points,grid,m,n,i,j);
flipped=true;
break;
}
}
}
//bfs寻找第二个岛屿,并把过程中经过的0赋值为2
int x,y;
int level=0;
while(!points.empty()){
//处理第一层0
++level;
int n_points=points.size();
while(n_points--){
//遍历第一层所有的点
auto [r,c]=points.front();
points.pop();
for(int k=0;k<4;++k){
x=r+direction[k],y=c+direction[k+1];
if(x>=0&&x<m&&y>=0&&y<n){
if(grid[x][y]==2){
//假如是2,啥也不做
continue;
}
if(grid[x][y]==1){
//假如遇到了另一座岛了,return level
return level;
}
if(grid[x][y]==0){
//假如遇到的还是0,那么就是下一层的0
points.push({
x,y});
//这个0变为2
grid[x][y]=2;
}
}
}
}
}
return 0;
}
//辅函数
void dfs(queue<pair<int,int>> &points,vector<vector<int>> &grid,
int m,int n,int i,int j)
{
if(i<0||j<0||i==m||j==n||grid[i][j]==2){
return;
}
if(grid[i][j]==0){
points.push({
i,j});
return;
}
grid[i][j]=2;
dfs(points,grid,m,n,i-1,j);
dfs(points,grid,m,n,i+1,j);
dfs(points,grid,m,n,i,j-1);
dfs(points,grid,m,n,i,j+1);
}
};
边栏推荐
- 质数(清华大学机试题)(DAY 86)
- The use of Conluce, an online document management system
- Navicat cannot connect to mysql super detailed processing method
- MySQL 用户授权
- php数组实现根据某个键值将相同键值合并生成新二维数组的方法
- [Other] DS5
- Programmers make money and practice, teach you how to do paid courses, self-media, paid articles and paid technical courses to make money
- Countdown (Source: Google Kickstart2020 Round C Problem A) (DAY 88)
- MYSQL-InnoDB的线程模型
- Basic syntax of MySQL DDL and DML and DQL
猜你喜欢
随机推荐
ezTrack-master使用教程
cmd(命令行)操作或连接mysql数据库,以及创建数据库与表
ClickHouse data insert, update and delete operations SQL
pwn-ROP
SRA数据下载方法总结
“tensorflow.keras.preprocessing“ has no attribute “image_dataset_from_directory“
MySQL user authorization
Seata exception: endpoint format should like ip:port
np.argsort()函数详细解析
mysql 时间字段默认设置为当前时间
解决phpstudy无法启动MySQL服务
postman 请求 post 调用 传 复合 json数据
[GO Language Basics] 1. Why do I want to learn Golang and the popularization of GO language entry
Different usage scenarios of subqueries as retrieval tables and the question of whether to add aliases
CISP-PTE真题演示
idea 编译protobuf 文件的设置使用
Different lower_case_table_names settings for server (‘1‘) and data dictionary (‘0‘) 解决方案
Difference between cookie and session
MySql模糊查询大全
k折交叉验证(k-fold Cross-validation)