GGHH ; G + H 必须 H 包含所有 H

解救小哈 - BFS 版本讲解

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

程序填空：

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

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

14
d = ((0, 1), (0, -1), (1, 0), (-1, 0))
15
q.append((sx, sy))
10 collapsed lines
16
step[sx][sy] = 0
17
while len(q) > 0:
18
    x, y = q.popleft()
19
    for i in range(4):
20
        nx, ny = x + d[i][0], y + d[i][1]
21
        if ok(nx, ny):
22
            q.append((nx, ny))
23
            step[nx][ny] = step[x][y] + 1
24

25
print(step[tx][ty])

Leaders

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

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

1
n = int(input())
2
s = input()
3
p = list(map(int, input().split()))
4
p = [(x - 1) for x in p]
5
fh, fg = -1, -1
6
lh, lg = -1, -1
7
for i in range(n):
8
    if s[i] == 'H':
9
        lh = i
10
        if fh == -1:
11
            fh = i
12
    else:
13
        lg = i
14
        if fg == -1:
15
            fg = i
11 collapsed lines
16
ans = 0
17
# GGHH ; G + H 必须 H 包含所有 H
18
if p[fh] >= lh: # fh and some g before that
19
    for i in range(fh):
20
        if p[i] >= fh or (i == 0 and p[i] >= lg):
21
            ans += 1
22
if p[fg] >= lg:
23
    for i in range(fg):
24
        if p[i] >= fg or (i == 0 and p[i] >= lh):
25
            ans += 1
26
print(ans)

1
n = int(input())
2
s = input()
3
p = list(map(int, input().split()))
4
p = [___ for x in p]
5
fh, fg = -1, -1
6
lh, lg = -1, -1
7
for i in range(n):
8
    if s[i] == 'H':
9
        ___
10
        if fh == -1:
11
            ___
12
    else:
13
        ___
14
        if fg == -1:
15
            ___
11 collapsed lines
16
ans = 0
17
# GGHH ; G + H 必须 H 包含所有 H
18
if p[fh] >= lh: # fh and some g before that
19
    for i in range(fh):
20
        if ___
21
            ans += 1
22
if p[fg] >= lg:
23
    for i in range(fg):
24
        if p[i] >= fg or (i == 0 and p[i] >= lh):
25
            ans += 1
26
print(ans)

# P2385 [USACO07FEB] Bronze Lilypad Pond B

https://www.luogu.com.cn/problem/P2385

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

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

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