GGHH ; G + H 必须 H 包含所有 H
2024-10-09
241013julyfunnoteswilliam工作解救小哈 - 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 2Leadershttps://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 Bhttps://www.luogu.com.cn/problem/P2385经典的 bfs 题目，但此题每个拓展点有八个方向进行选择，类似于象棋马步创建空队列
将起点放入队列
while 队列不空:
取出并弹出队首 u
将 u 的八个方向判断是否在边界内且为莲花或终点
将可行且没走过的点加入队列
输出终点距离
python deque:
push: d.append(4) / a.appendleft(4)
front: d[0]
pop: d.popleft() / d.pop(