Skip to content

课堂计划

解救小哈 - BFS 版本讲解

  • 使用队列存储到达过的点，对队列中的每一个点再向四个方向拓展。
  • 最优性：最近的点会最早进入队列

程序填空：

from collections import deque
q = deque()
n, m, t = map(int, input().split())
sx, sy, tx, ty = map(int, input().split())
a = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
step = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
for _ in range(t):
    x, y = map(int, input().split())
    a[x][y] = 1

def ok(x, y):
    return 1 <= x <= n and 1 <= y <= m and a[x][y] == 0 and step[x][y] == -1

d = ((0, 1), (0, -1), (1, 0), (-1, 0))
q.append((sx, sy))
step[sx][sy] = 0
while len(q) > 0:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        if ok(nx, ny):
            q.append((nx, ny))
            step[nx][ny] = step[x][y] + 1

print(step[tx][ty])


3 3 2
1 1 3 1
2 1
2 2

Leaders

https://usaco.org/index.php?page=viewproblem2&cpid=1275

观察规律：若 G + H 组合，则 H 必须包含后面全部 H，且前面的 G 是第一个且包含全部 G，或 G 包含此 H。判断时，使用最早出现的 H 和 G 判断

n = int(input())
s = input()
p = list(map(int, input().split()))
p = [(x - 1) for x in p]
fh, fg = -1, -1
lh, lg = -1, -1
for i in range(n):
    if s[i] == 'H':
        lh = i
        if fh == -1:
            fh = i
    else:
        lg = i
        if fg == -1:
            fg = i
ans = 0
# GGHH ; G + H 必须 H 包含所有 H
if p[fh] >= lh: # fh and some g before that
    for i in range(fh):
        if p[i] >= fh or (i == 0 and p[i] >= lg):
            ans += 1
if p[fg] >= lg:
    for i in range(fg):
        if p[i] >= fg or (i == 0 and p[i] >= lh):
            ans += 1
print(ans)

n = int(input())
s = input()
p = list(map(int, input().split()))
p = [___ for x in p]
fh, fg = -1, -1
lh, lg = -1, -1
for i in range(n):
    if s[i] == 'H':
        ___
        if fh == -1:
            ___
    else:
        ___
        if fg == -1:
            ___
ans = 0
# GGHH ; G + H 必须 H 包含所有 H
if p[fh] >= lh: # fh and some g before that
    for i in range(fh):
        if ___
            ans += 1
if p[fg] >= lg:
    for i in range(fg):
        if p[i] >= fg or (i == 0 and p[i] >= lh):
            ans += 1
print(ans)

# P2385 [USACO07FEB] Bronze Lilypad Pond B

经典的 bfs 题目，但此题每个拓展点有八个方向进行选择，类似于象棋马步

创建空队列
将起点放入队列
while 队列不空:
    取出并弹出队首 u
    将 u 的八个方向判断是否在边界内且为莲花或终点
        将可行且没走过的点加入队列
输出终点距离

python deque:
push: d.append(4) / a.appendleft(4)
front: d[0]
pop: d.popleft() / d.pop()