02802: 小游戏
bfs, http://cs101.openjudge.cn/practice/02802/
一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小游戏。
游戏在一个分割成w * h个正方格子的矩形板上进行。如图所示，每个正方格子上可以有一张游戏卡片，当然也可以没有。
当下面的情况满足时，我们认为两个游戏卡片之间有一条路径相连：
路径只包含水平或者竖直的直线段。路径不能穿过别的游戏卡片。但是允许路径临时的离开矩形板。下面是一个例子：
这里在 (1, 3)和 (4, 4)处的游戏卡片是可以相连的。而在 (2, 3) 和 (3, 4) 处的游戏卡是不相连的，因为连接他们的每条路径都必须要穿过别的游戏卡片。
你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。
输入
输入包括多组数据。一个矩形板对应一组数据。每组数据包括的第一行包括两个整数w和h (1 <= w, h <= 75)，分别表示矩形板的宽度和长度。下面的h行，每行包括w个字符，表示矩形板上的游戏卡片分布情况。使用‘X’表示这个地方有一个游戏卡片；使用空格表示这个地方没有游戏卡片。
之后的若干行上每行上包括4个整数x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)。给出两个卡片在矩形板上的位置（注意：矩形板左上角的坐标是(1, 1)）。输入保证这两个游戏卡片所处的位置是不相同的。如果一行上有4个0，表示这组测试数据的结束。
如果一行上给出w = h = 0，那么表示所有的输入结束了。
输出
对每一个矩形板，输出一行“Board #n:”，这里n是输入数据的编号。然后对每一组需要测试的游戏卡片输出一行。这一行的开头是“Pair m: ”，这里m是测试卡片的编号（对每个矩形板，编号都从1开始）。接下来，如果可以相连，找到连接这两个卡片的所有路径中包括线段数最少的路径，输出“k segments.”，这里k是找到的最优路径中包括的线段的数目；如果不能相连，输出“impossible.”。
每组数据之后输出一个空行。
样例输入
5 4
XXXXX
X X
XXX X
XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0样例输出
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.来源：翻译自Mid-Central European Regional Contest 1999的试题
刘思昊 24工学院。提供了hack数据，会导致很多之前AC的程序WA。
原因应该是左下那条路先到达终点下面的那个点并且抢占了inq位置，导致后来的左上路线没法进入queue。
使用defaultdict记录seg，以相同方向到达同一个点是如果seg>=原来的则不值得讨论无需入列，否则还需进一步讨论
sample2 input:
8 8 XXXXXXXX XX X X XXXX X X XXX X XX X X XXXX X X XXXX X XXXXXXXX 2 2 5 4 0 0 0 0 0 0Sample2 output:
Board #1: Pair 1: 4 segments.Sample3 input:
8 9 XXXXXXXX XX X X XXXX X X XXXX X X X X X XX X X XXXX X X XXXX X XXXXXXXX 2 2 5 4 0 0 0 0 0 0Sample3 output:
Board #1: Pair 1: 4 segments.
bfs
这个题目比较麻烦，因为外圈还可以走，需要在输入矩阵包一圈。另外，就是行列与我们平时练习行列刚好反着。
因为没有走到end之前的线段最短，不能保证总的线段最短。需要穷举队列，找到的最短都append到ans列表，最后min(ans)。
from collections import deque
from collections import defaultdict
def bfs(start, end, grid, h, w):
queue = deque([start])
in_queue = defaultdict(lambda: float('inf'))
dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
min_x = float('inf')
while queue:
x, y, d, seg = queue.popleft()
for i, (dx, dy) in enumerate(dirs):
nx, ny = x + dx, y + dy
new_seg = seg if i == d else seg + 1
if (nx, ny) == end:
min_x = min(min_x, new_seg)
continue
if (0 <= nx < h + 2 and 0 <= ny < w + 2 and new_seg<in_queue[(nx,ny,i)]
and grid[nx][ny] != 'X'):
in_queue[(nx, ny, i)] = new_seg
queue.append((nx, ny, i, new_seg))
return min_x
board_num = 1
while True:
w, h = map(int, input().split())
if w == h == 0:
break
grid = [' ' * (w + 2)] + [' ' + input() + ' ' for _ in range(h)] + [' ' * (w + 2)]
print(f"Board #{board_num}:")
pair_num = 1
while True:
y1, x1, y2, x2 = map(int, input().split())
if x1 == y1 == x2 == y2 == 0:
break
start = (x1, y1, -1, 0)
end = (x2, y2)
seg = bfs(start, end, grid, h, w)
if seg == float('inf'):
print(f"Pair {pair_num}: impossible.")
else:
print(f"Pair {pair_num}: {seg} segments.")
pair_num += 1
print()
board_num += 1其实所有求最短、最长的问题都能用heapq实现，在图搜索中搭配bfs尤其好用。
利用heap优先队列的做法，因为每次都取当前队列中线段最小值前进，可以保证最后总的线段最短。这个实际上是Dijkstra。
# 23 工学院 苏王捷
import heapq
from collections import defaultdict
num1 = 1
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
print(f"Board #{num1}:")
martix = [[" "] * (w + 2)] + [[" "] + list(input()) + [" "] for _ in range(h)] + [[" "] * (w + 2)]
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
num2 = 1
while True:
x1, y1, x2, y2 = map(int, input().split())
if x1 == 0 and x2 == 0 and y1 == 0 and y2 == 0:
break
queue, flag = [], False
in_queue = defaultdict(lambda: float("inf"))
heapq.heappush(queue, (0, x1, y1, -1))
martix[y2][x2] = " "
in_queue[(-1, x1, y1)] = 0
while queue:
step, x, y, dirs = heapq.heappop(queue)
if x == x2 and y == y2:
flag = True
break
for i, (dx, dy) in enumerate(dir):
px, py = x + dx, y + dy
new_step = step + (dirs != i)
if 0 <= px <= w + 1 and 0 <= py <= h + 1 and new_step < in_queue[(i, px, py)] and martix[py][px] != "X":
in_queue[(i, px, py)] = new_step
heapq.heappush(queue, (new_step, px, py, i))
if flag:
print(f"Pair {num2}: {step} segments.")
else:
print(f"Pair {num2}: impossible.")
martix[y2][x2] = "X"
num2 += 1
print()
num1 += 1以下两份代码，在hack数据上都会WA。
python# 23 工学院 苏王捷 import heapq num1 = 1 while True: w, h = map(int, input().split()) if w == 0 and h == 0: break print(f"Board #{num1}:") martix = [[" "] * (w + 2)] + [[" "] + list(input()) + [" "] for _ in range(h)] + [[" "] * (w + 2)] dir = [(0, 1), (0, -1), (1, 0), (-1, 0)] num2 = 1 while True: x1, y1, x2, y2 = map(int, input().split()) if x1 == 0 and x2 == 0 and y1 == 0 and y2 == 0: break queue, flag = [], False in_queue = set() heapq.heappush(queue, (0, x1, y1, -1)) martix[y2][x2] = " " in_queue.add((-1, x1, y1)) while queue: step, x, y, dirs = heapq.heappop(queue) if x == x2 and y == y2: flag = True break for i, (dx, dy) in enumerate(dir): px, py = x + dx, y + dy if 0 <= px <= w + 1 and 0 <= py <= h + 1 and (i, px, py) not in in_queue and martix[py][px] != "X": in_queue.add((i, px, py)) heapq.heappush(queue, (step + (dirs != i), px, py, i)) if flag: print(f"Pair {num2}: {step} segments.") else: print(f"Pair {num2}: impossible.") martix[y2][x2] = "X" num2 += 1 print() num1 += 1bfs
pythonfrom collections import deque def bfs(start, end, grid, h, w): queue = deque([start]) in_queue = set() dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)] ans = [] while queue: x, y, d_i_r, seg = queue.popleft() # print(x,y,end) if (x, y) == end: # return seg ans.append(seg) break for i, (dx, dy) in enumerate(dirs): nx, ny = x + dx, y + dy if 0 <= nx < h + 2 and 0 <= ny < w + 2 and ((nx, ny, i) not in in_queue): new_dir = i new_seg = seg if new_dir == d_i_r else seg + 1 if (nx, ny) == end: # return new_seg ans.append(new_seg) continue if grid[nx][ny] != 'X': in_queue.add((nx, ny, i)) queue.append((nx, ny, new_dir, new_seg)) if len(ans) == 0: return -1 else: return min(ans) board_num = 1 while True: w, h = map(int, input().split()) if w == h == 0: break # grid = [[' '] * (w + 2)] + \ # [[' '] + list(input()) + [' '] for _ in range(h)] + \ # [[' '] * (w + 2)] grid = [' ' * (w + 2)] + [' ' + input() + ' ' for _ in range(h)] + [' ' * (w + 2)] print(f"Board #{board_num}:") pair_num = 1 while True: y1, x1, y2, x2 = map(int, input().split()) if x1 == y1 == x2 == y2 == 0: break start = (x1, y1, -1, 0) end = (x2, y2) seg = bfs(start, end, grid, h, w) if seg == -1: print(f"Pair {pair_num}: impossible.") else: print(f"Pair {pair_num}: {seg} segments.") pair_num += 1 print() board_num += 1
《算法基础。。》上面讲到4.3例题：小游戏，书上给出的是dfs。但是经过同学和助教调试，发现dfs与先沿着哪个邻居出发有关，导致剪枝可能失效。因为可能拿不到一个相对较好的结果，便于比较剪枝。所以最好用bfs完成。
dfs写的的代码，可以通过hack的数据，因为有回溯。但是dfs可能在其他情况超时。
import sys
sys.setrecursionlimit(1000000)
d=[(0,-1),(0,1),(-1,0),(1,0)]
H,L,ha,la,hb,lb,MIN=0,0,0,0,0,0,0
b=0
def dfs(h,l,dire,step):
global H,L,hb,lb,MIN,b
if h==hb and l==lb:
if step<MIN:
MIN=step
return
if step>=MIN:
return
for i in d:
hh,ll=h+i[0],l+i[1]
if hh>=0 and hh<=H+1 and ll>=0 and ll<=L+1 and b[hh][ll]==' ':
b[hh][ll]='X'
if dire!=i:
dfs(hh,ll,i,step+1)
else:
dfs(hh,ll,i,step)
b[hh][ll]=' '
k1=0
while True:
k1+=1
L,H=map(int,input().split())
if L==0:
break
print("Board #{}:".format(k1))
b=[[' ']*(L+2)]
for _ in range(H):
b.append([' ']+list(input())+[' '])
b.append([' ']*(L+2))
k2=0
while True:
k2+=1
la,ha,lb,hb=map(int,input().split())
MIN=float('inf')
if la==0:
break
b[hb][lb]=' '
dfs(ha,la,(0,0),0)
b[hb][lb]='X'
if MIN==float('inf'):
print("Pair {}: impossible.".format(k2))
else:
print("Pair {}: {} segments.".format(k2,MIN))
print()