T20741: 两座孤岛最短距离
dfs, bfs, dijkstra, http://cs101.openjudge.cn/pctbook/T20741
给一个由1跟0组成的方形地图，1代表土地，0代表水域
相邻(上下左右4个方位当作相邻)的1组成孤岛
现在你可以将0转成1，搭建出一个链接2个孤岛的桥
请问最少要将几个0转成1，才能建成链接孤岛的桥。
题目中恰好有2个孤岛(顾答案不会是0)
输入
一个正整数n，代表几行输入 n行0跟1字串
输出
一个正整数k，代表最短距离
样例输入
3
110
000
001样例输出
2提示
样例输入中的两个孤岛最短距离为2
dfs + bfs
将第一个边缘作为多个起点，可以同时存入bfs的队列q中，由于这几个起点是同步开始搜索的，所以第一个搜到的一定对应最短值。
这道题目其实基本思路很好想，但是想要优化到不超时还是需要下功夫的。首先，只需要将找到的第一个孤岛打上标记，第二个不用管。其次，可以直接在找到第一个孤岛之后直接开始bfs，不用再次遍历列表了。
python
from collections import deque
def dfs(x, y, grid, n, queue, directions):
""" Mark the connected component starting from (x, y) as visited using DFS. """
grid[x][y] = 2 # Mark as visited
queue.append((x, y))
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
dfs(nx, ny, grid, n, queue, directions)
def bfs(grid, n, queue, directions):
""" Perform BFS to find the shortest path to another component. """
distance = 0
while queue:
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n:
if grid[nx][ny] == 1:
return distance
elif grid[nx][ny] == 0:
grid[nx][ny] = 2 # Mark as visited
queue.append((nx, ny))
distance += 1
return distance
def main():
n = int(input())
grid = [list(map(int, input())) for _ in range(n)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque()
# Start DFS from the first '1' found and use BFS from there
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
dfs(i, j, grid, n, queue, directions)
return bfs(grid, n, queue, directions)
if __name__ == "__main__":
print(main())python
from collections import deque
class Solution:
def shortestBridge(self, grid) -> int:
m, n = len(grid), len(grid[0])
points = deque()
def dfs(points, grid, m, n, i, j):
if i < 0 or i == m or j < 0 or j == n or grid[i][j] == 2:
return
if grid[i][j] == 0:
points.append((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)
flag = False
for i in range(m):
if flag:
break
for j in range(n):
if grid[i][j] == 1:
dfs(points, grid, m, n, i, j)
flag = True
break
x, y, count = 0, 0, 0
while points:
count += 1
n_points = len(points)
while n_points > 0:
point = points.popleft()
r, c = point[0], point[1]
for k in range(4):
x, y = r + direction[k], c + direction[k + 1]
if x >= 0 and y >= 0 and x < m and y < n:
if grid[x][y] == 2:
continue
if grid[x][y] == 1:
return count
points.append((x, y))
grid[x][y] = 2
n_points -= 1
return 0
direction = [-1, 0, 1, 0, -1]
n = int(input())
grid = []
for i in range(n):
row = list(map(int, list(input())))
grid.append(row)
print(Solution().shortestBridge(grid))python
import collections
def main():
n=int(input())
#grid=[[0]*(n+2)]
grid=[]
for i in range(n):
p=list(int(x) for x in input())
#p.insert(0,0)
#p.append(0)
grid.append(p)
grid.append([0]*(n+2))
visited = [[False for _ in range(n)] for _ in range(n)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
sr, sc = -1, -1
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
sr, sc = r, c
break
q = collections.deque()
q.append((sr, sc))
visited[sr][sc] = True
while q:
r, c = q.popleft()
for dr, dc in dirs:
nr = r + dr
nc = c + dc
if 0 <= nr < n and 0 <= nc < n:
if grid[nr][nc] == 1 and visited[nr][nc] == False:
visited[nr][nc] = True
q.append((nr, nc))
#------------ 计算最短距离。多源bfs
for r in range(n):
for c in range(n):
if visited[r][c] == True and grid[r][c] == 1:
q.append((r, c))
step = 0
while q:
curLen = len(q)
for _ in range(curLen):
r, c = q.popleft()
for dr, dc in dirs:
nr = r + dr
nc = c + dc
if 0 <= nr < n and 0 <= nc < n and visited[nr][nc] == False:
visited[nr][nc] = True
if grid[nr][nc] == 1:
return step
q.append((nr, nc))
step += 1
return step
print(main())思路：这题时间卡的超极严。。。简直是不能做任何多的一点操作，要用Dijkstra算法并且还要最简化。权值判断即为从1到1为0，1到0和0到0为1。
用 Dijkstra算法时，由于每次处理的都是当前步数最小的，说明刚开始是先处理同一个岛上的点，假如出现从 0 到 1 的情况时，说明已经到另一个岛上了，可以直接返回当前步数。
python
# 俞天麒 24物理学院
import heapq
n=int(input())
land=[]
dir=[[0,1],[0,-1],[1,0],[-1,0]]
for i in range(n):
land.append(input())
visited=[[True]*(len(land[i])) for i in range(len(land))]
def find(x1,y1):
pos=[]
heapq.heappush(pos,(0,x1,y1))
visited[x1][y1]=False
while pos:
step,x,y=heapq.heappop(pos)
#print(step,x,y)
if land[x][y]=="1" and step!=0:
return step
for dx,dy in dir:
nx,ny=x+dx,y+dy
if 0<=nx<n and 0<=ny<len(land[nx]) and visited[nx][ny]:
visited[nx][ny]=False
if land[nx][ny]==land[x][y] and land[x][y]!="0":
heapq.heappush(pos,(step,nx,ny))
else:
heapq.heappush(pos,(step+1,nx,ny))
mark=False
for i in range(n):
for j in range(len(land[i])):
if land[i][j]=="1":
print(find(i,j)-1)
exit()python
#吴迪、24物理学院
"""
Dijstra算法的短代码优化版本，其实没有必要把所有1都找出来，只要找到一个1，以之为出发点，
遇到1步数不变，遇到0步数+1，这样同一个岛内的step都是一样的，一个岛就相当于一个点
"""
n=int(input())
ma=[list(map(int,input())) for _ in range(n)]
m,dire=len(ma[0]),[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(n):
for j in range(m):
if ma[i][j]==1:
x1,y1=i,j
import heapq
def dijkstra(x1,y1):
q,visited=[],[[False]*m for _ in range(n)]
heapq.heappush(q,(0,x1,y1))
while q:
step,x,y=heapq.heappop(q)
if visited[x][y]:
continue
visited[x][y] = True
if ma[x][y]==1 and step!=0:
return step
for dx,dy in dire:
if 0<=x+dx<n and 0<=y+dy<m and not visited[x+dx][y+dy]:
heapq.heappush(q,(step+1-ma[x+dx][y+dy],x+dx,y+dy))
print(dijkstra(x1,y1))思路：一个bfs找第一个岛，另一个从第一个岛找第二个岛。基本都是按套路来，只是visited可以共享，感觉是唯一一个优化
python
# 王梓航，24物理学院
import heapq
dir = [(-1,0),(1,0),(0,1),(0,-1)]
n = int(input())
a = [list(map(int,list(input()))) for _ in range(n)]
m = len(a[0])
first=set([])
for i in range(n):
for j in range(m):
if a[i][j]==1:
visited=[[False]*m for _ in range(n)]
visited[i][j]=True
queue=[]
heapq.heappush(queue,(i,j))
first.add((i,j))
while queue:
x,y=heapq.heappop(queue)
for dx,dy in dir:
px,py=x+dx,y+dy
if 0<=px<n and 0<=py<m and not visited[px][py] and a[px][py]==1:
visited[px][py]=True
first.add((px,py))
heapq.heappush(queue,[px,py])
queue = []
for p, q in first:
heapq.heappush(queue, [0, p, q])
while queue:
count, x, y = heapq.heappop(queue)
count += 1
for dx, dy in dir:
px, py = x + dx, y + dy
if 0 <= px < n and 0 <= py < m and not visited[px][py]:
visited[px][py] = True
heapq.heappush(queue, [count, px, py])
if a[px][py] == 1:
print(count-1)
exit(0)先通过一次DFS遍历第一座孤岛，存储其所有点的坐标，随后使之“沉没”。在扫描到陆地（必属于第二座孤岛）后，计算其与之前存储的所有点间最短路径的长度，取最小值即可。
c++
// 周晟昱 24工学院
#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
int n, ans = 1000000000;
std::vector<std::vector<int>> mp;
std::vector<std::pair<int, int>> land1;
void build_island(const int &x, const int &y)
{
if (mp[x][y] == 0)
return;
land1.push_back(std::make_pair(x, y));
mp[x][y] = 0;
if (x - 1 >= 0)
build_island(x - 1, y);
if (x + 1 < n)
build_island(x + 1, y);
if (y - 1 >= 0)
build_island(x, y - 1);
if (y + 1 < n)
build_island(x, y + 1);
}
int main()
{
char c;
std::cin >> n;
mp.resize(n, std::vector<int>(n, 0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
std::cin >> c;
mp[i][j] = c - '0';
}
bool flag = true;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (mp[i][j])
{
if (flag)
{
build_island(i, j);
flag = false;
}
else
for (auto &[a, b] : land1)
ans = std::min(ans, std::abs(i - a) + std::abs(j - b) - 1);
}
std::cout << ans << std::endl;
return 0;
}思路：
- 学语法千日用语法一时，
yield表达式真好使 - 把两个岛的边界找出来，存起来，找曼哈顿距离最小值，可过
- 可以转成集合避免重复计算耽误时间
python
# 颜鼎堃 24工学院
DIRECTIONS = ((0, 1), (0, -1), (1, 0), (-1, 0))
def dfs(x, y):
stack = [(x, y)]
while stack:
x1, y1 = stack.pop()
isl[x1][y1] = "0"
for dx, dy in DIRECTIONS:
nx, ny = x1 + dx, y1 + dy
if isl[nx][ny] == "1":
stack.append((nx, ny))
else:
yield (x1, y1)
n = int(input())
isborder = []
cnt = 0
isl = [["0" for i in range(n+2)]] + [["0"] + list(input()) + ["0"] for i in range(n)] + [["0" for i in range(n+2)]]
for i in range(1, 1 + n):
while "1" in isl[i]:
cnt += 1
isborder.append(set(dfs(i, isl[i].index("1"))))
if cnt == 2:
break
if cnt == 2:
break
print(min([abs(a - c) + abs(b - d) - 1 for a, b in isborder[0] for c, d in isborder[1]]))