how to

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

Oct 9, 2024
notesjulyfun工作william241013
4 Minutes
606 Words

解救小哈 - 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])
1
3 3 2
2
1 1 3 1
3
2 1
4
2 2

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

经典的 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()
Article title:GGHH ; G + H 必须 H 包含所有 H
Article author:Julyfun
Release time:Oct 9, 2024
Copyright 2025
Sitemap