题目列表
-
多源BFS 173. 矩阵距离 30:11
-
最小步数模型 AcWing 1107. 魔板 42:57
-
双端队列广搜 AcWing 175. 电路维修 01:23:29
BFS 队列性质
- 单调性
- 双段性
题目解析
- 多源BFS 173. 矩阵距离 30:11
要点：队列初始化时候放入多个源即可
n, m = map(int, input().split())
N = n + 1
M = N * N
g = [input() for _ in range(n)]
q = [0] * M
dist = [[-1] * N for _ in range(N)]
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
def bfs():
hh, tt = 0, 0
for i in range(n):
for j in range(m):
if g[i][j] == '1':
dist[i][j] = 0
q[tt] = (i,j)
tt += 1
while hh < tt:
x, y = q[hh]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m or dist[nx][ny] != -1:
continue
dist[nx][ny] = dist[x][y] + 1
q[tt] = (nx, ny)
tt += 1
hh += 1
bfs()
[print(' '.join([str(i) for i in dist[i][:m]])) for i in range(n)]
- 最小步数模型 AcWing 1107. 魔板 42:57
要点：状态的编码和解码
from queue import deque
g = [[0] * 4 for _ in range(2)]
dist = dict()
pre = dict()
def set(state):
g[0], g[1] = list(state[:4]), list(state[4:][::-1])
def get():
return ''.join(g[0] + g[1][::-1])
def move0(state):
set(state)
for i in range(4): g[0][i], g[1][i] = g[1][i], g[0][i]
return get()
def move1(state):
set(state)
g[0], g[1] = [g[0][-1]] + g[0][:-1], [g[1][-1]] + g[1][:-1]
return get()
def move2(state):
set(state)
g[0][1], g[1][1], g[1][2], g[0][2] = g[1][1], g[1][2], g[0][2], g[0][1]
return get()
def bfs(start, end):
if start == end: return 0
q = deque()
q.appendleft(start)
dist[start] = 0
while q:
t = q.popleft()
for tp, mi in zip('ABC', [move0(t), move1(t), move2(t)]):
if mi not in dist:
dist[mi] = dist[t] + 1
pre[mi] = (tp, t)
q.append(mi)
if mi == end: return dist[end]
start, end = '12345678', input().replace(' ', '')
step = bfs(start, end)
print(step)
res = ''
while end != start:
res += pre[end][0]
end = pre[end][1]
if step > 0: print(res[::-1])
- 双端队列广搜 AcWing 175. 电路维修 01:23:29
要点：使用双端队列进行包含0距离边的图BFS，距离为0的结点push_front，距离非0的结点push_back. 维持队列的单调性和两段性.
from queue import deque
cs = '\\/\\/'
dx, dy = (-1 ,-1, 1, 1), (-1, 1, 1, -1)
ix, iy = (-1, -1, 0, 0), (-1, 0, 0, -1)
def bfs():
dist = [[float('inf')] * M for _ in range(N)]
st = set()
dist[0][0] = 0
q = deque()
q.append((0, 0))
while q:
t = q.popleft()
if t in st: continue
st.add(t)
for i in range(4):
a, b = t[0] + dx[i], t[1] + dy[i]
if a < 0 or a > n or b < 0 or b > m: continue
ca, cb = t[0] + ix[i], t[1] + iy[i]
d = dist[t[0]][t[1]] + (g[ca][cb] != cs[i])
if d < dist[a][b]:
dist[a][b] = d
q.appendleft((a, b)) if g[ca][cb] == cs[i] else q.append((a, b))
return dist[n][m]
T = int(input())
while T:
n, m = map(int, input().split())
N, M = n + 1, m + 1
g = [input() for _ in range(n)]
t = bfs()
print("NO SOLUTION") if t == float('inf') else print(t)
T -= 1
