25572: 螃蟹采蘑菇
http://cs101.openjudge.cn/practice/25572/
“采蘑菇的小螃蟹，背着一个大竹框”
一只螃蟹小呆想要从迷宫中的一个地方走到另一个地方采蘑菇，请你帮小呆判断一下它能否到达
迷宫所在的区域为一个n*n的格子矩阵，0的格子表示路，1的格子表示不能穿过的墙体，整个区域的外围也由墙体包围不能穿过。
小呆的身体占据相邻的两个格子，且小呆只能沿前后左右四个方向平移，不能斜着走也不能旋转，用两个数字5表示小呆的初始位置，用一个数字9表示蘑菇的位置，即小呆想要到达的地方（只要小呆两侧身体的任意一侧能够到达蘑菇的位置即可认为能够到达）
输入
第一行一个正整数n ( n < 30 )，表示迷宫区域的大小 接下来n行，每行n个整数，代表迷宫各个位置的情况。
输出
如果小呆能够到达终点，则输出yes 否则输出no
样例输入
Sample Input1:
6
0 0 0 0 0 9
0 0 1 0 1 1
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 1 5 5
Sample Output1:
yes样例输出
Sample Input2:
6
0 0 0 0 0 9
0 0 1 0 1 1
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 1 0 5
0 0 0 1 0 5
Sample Output2:
no提示 tags: bfs, dfs
来源: 2022fall-cs101, gdr
bfs，只是多加了一些东西，没有本质区别。
python
from collections import deque
# 定义四个方向：右、下、左、上
dire = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def bfs(a, x1, y1, x2, y2):
visit = set() # 使用集合来避免重复访问
queue = deque([(x1, y1, x2, y2)])
visit.add((x1, y1, x2, y2)) # 初始点加入访问集合
while queue:
xa, ya, xb, yb = queue.popleft()
# 遍历四个方向
for xi, yi in dire:
# 计算新位置
nx1, ny1 = xa + xi, ya + yi
nx2, ny2 = xb + xi, yb + yi
# 判断新位置是否合法
if 0 <= nx1 < a and 0 <= ny1 < a and 0 <= nx2 < a and 0 <= ny2 < a:
if (nx1, ny1, nx2, ny2) not in visit and Matrix[nx1][ny1] != 1 and Matrix[nx2][ny2] != 1:
# 加入队列并标记访问
queue.append((nx1, ny1, nx2, ny2))
visit.add((nx1, ny1, nx2, ny2))
# 检查是否到达目标
if Matrix[nx1][ny1] == 9 or Matrix[nx2][ny2] == 9:
return True
return False
# 读取输入
a = int(input())
Matrix = [list(map(int, input().split())) for _ in range(a)]
# 找到第一个和第二个 '5' 的位置
x1, y1, x2, y2 = -1, -1, -1, -1
found_first = False
for i in range(a):
for j in range(a):
if Matrix[i][j] == 5:
if not found_first:
x1, y1 = i, j
Matrix[i][j] = 0 # 标记为已访问
found_first = True
else:
x2, y2 = i, j
Matrix[i][j] = 0 # 标记为已访问
break
if x2 != -1: # 如果第二个 5 已经找到
break
# 运行 BFS 检查是否可以从 (x1, y1) 到 (x2, y2)
check = bfs(a, x1, y1, x2, y2)
print('yes' if check else 'no')思路:一位信科学长告诉我的，别管有几个点要移动，每个点都去判定就行，果真能行，这题就变成了一题很简单的bfs，之前做过一次，还是参照着解答，写了type1 type2区分横的竖的，如今看来没必要
python
# 马凱权 24元培学院
from collections import deque
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bfs(s_x1, s_y1, s_x2, s_y2):
if not ((abs(s_x1 - s_x2) == 1 and s_y1 == s_y2) or (s_x1 == s_x2 and abs(s_y1 - s_y2) == 1)):
return False
q = deque()
q.append((s_x1, s_y1, s_x2, s_y2))
inq = set()
inq.add((s_x1, s_y1, s_x2, s_y2))
while q:
x1, y1, x2, y2 = q.popleft()
if maze[x1][y1] == 9 or maze[x2][y2] == 9:
return True
for dx, dy in move:
nx1, ny1 = x1 + dx, y1 + dy
nx2, ny2 = x2 + dx, y2 + dy
if 0 <= nx1 < n and 0 <= ny1 < n and 0 <= nx2 < n and 0 <= ny2 < n:
if maze[nx1][ny1] != 1 and maze[nx2][ny2] != 1:
if (nx1, ny1, nx2, ny2) not in inq:
inq.add((nx1, ny1, nx2, ny2))
q.append((nx1, ny1, nx2, ny2))
return False
n = int(input())
maze = [list(map(int, input().split())) for _ in range(n)]
a = []
for i in range(n):
for j in range(n):
if maze[i][j] == 5:
a.append([i, j])
if len(a) == 2:
result = bfs(a[0][0], a[0][1], a[1][0], a[1][1])
print('yes' if result else 'no')
else:
print('no')python
# 23n2300011427 高铭泽 物理学院，25572:螃蟹采蘑菇
from collections import deque
n = int(input())
mat = []
for i in range(n):
mat.append(list(map(int, input().split())))
a = []
for i in range(n):
for j in range(n):
if mat[i][j] == 5:
a.append([i, j])
lx = a[1][0] - a[0][0]
ly = a[1][1] - a[0][1]
dire = [[-1, 0], [0, 1], [1, 0], [0, -1]]
v = [[0] * n for i in range(n)]
def bfs(x, y):
v[x][y] = 1
quene = deque([(x, y)])
while quene:
x, y = quene.popleft()
if (mat[x][y] == 9 and mat[x + lx][y + ly] != 1) or \
(mat[x][y] != 1 and mat[x + lx][y + ly] == 9):
return 'yes'
for i in range(4):
dx = x + dire[i][0]
dy = y + dire[i][1]
if 0 <= dx < n and 0 <= dy < n and 0 <= dx + lx < n \
and 0 <= dy + ly < n and v[dx][dy] == 0 \
and mat[dx][dy] != 1 and mat[dx + lx][dy + ly] != 1:
quene.append([dx, dy])
v[dx][dy] = 1
return 'no'
print(bfs(a[0][0], a[0][1]))python
# 蒋子轩，25572:螃蟹采蘑菇
def dfs(x,y):
if matrix[x][y]==9:
print('yes')
exit()
for k in range(4):
nx,ny=x+dx[k],y+dy[k]
if 0<=nx<n and 0<=ny<n and (nx,ny) not in visited and matrix[nx][ny]!=1:
if type==1:
if nx==n-1 or matrix[nx+1][ny]==1:
continue
if matrix[nx+1][ny]==9:
print('yes')
exit()
else:
if ny==n-1 or matrix[nx][ny+1]==1:
continue
if matrix[nx][ny+1]==9:
print('yes')
exit()
visited.add((nx,ny))
dfs(nx,ny)
n=int(input())
dx=[1,0,0,-1]
dy=[0,1,-1,0]
matrix=[list(map(int,input().split())) for _ in range(n)]
visited=set()
for i in range(n):
for j in range(n):
if matrix[i][j]==5:
if i<n-1 and matrix[i+1][j]==5:
type=1
else:
type=2
dfs(i,j)
print('no')
exit()思路：bfs,先遍历矩阵找到两个起点，再找出两者关系，之后只对其中一个进行重点关注
python
from collections import deque
n=int(input())
maze=[list(map(int,input().split())) for _ in range(n)]
start=[]
for i in range(n):
for j in range(n):
if maze[i][j]==5:
start.append((i,j))
delta_x=start[1][0]-start[0][0]
delta_y=start[1][1]-start[0][1]
visited=set()
visited.add((start[0][0],start[0][1]))
def is_valid(r,c):
if 0<=r<n and 0<=c<n and (r,c) not in visited and maze[r][c]!=1 and 0<=r+delta_x<n and 0<=c+delta_y<n and maze[r+delta_x][c+delta_y]!=1:
return 1
else:
return 0
dx=[0,0,1,-1]
dy=[1,-1,0,0]
stack=deque()
stack.append((start[0][0],start[0][1]))
while stack:
front_x,front_y=stack.popleft()
if maze[front_x][front_y]==9 or maze[front_x+delta_x][front_y+delta_y]==9:
print('yes')
exit()
for i in range(4):
nx,ny=front_x+dx[i],front_y+dy[i]
if is_valid(nx,ny):
visited.add((nx,ny))
stack.append((nx,ny))
print('no')python
from collections import deque
directions=[[0,1],[0,-1],[1,0],[-1,0]]
o=int(input())
a=[list(map(int,input().split())) for _ in range(o)]
def bfs(e,f,g,h,end1,end2):
q=deque()
ind=set()
q.append((e,f,g,h))
ind.add((e,f,g,h))
while q:
m,n,j,k=q.popleft()
if (m==end1 and n==end2) or (j==end1 and k==end2):
return "yes"
for dx,dy in directions:
km=m+dx;kn=n+dy
kj=j+dx;kk=k+dy
if 0<=km<o and 0<=kn<o and 0<=kj<o and 0<=kk<o and a[km][kn]!=1 and a[kj][kk]!=1 and (km,kn,kj,kk) not in ind:
q.append((km,kn,kj,kk))
ind.add((km,kn,kj,kk))
return "no"
b=[]
end_1=0
end_2=0
for i in range(o):
for j in range(o):
if a[i][j]==5:
b.append(i)
b.append(j)
elif a[i][j]==9:
end_1=i;end_2=j
aa,bb,cc,dd=b
print(bfs(aa,bb,cc,dd,end_1,end_2))思路：只把前面那个点入队，并通过位置关系考虑另一个点
python
# 彭凌越 24光华管理学院
from collections import deque
n = int(input())
mat = []
for i in range(n):
mat.append(list(map(int, input().split())))
a = []
for i in range(n):
for j in range(n):
if mat[i][j] == 5:
a.append([i, j])
lx = a[1][0] - a[0][0]
ly = a[1][1] - a[0][1]
dire = [[-1, 0], [0, 1], [1, 0], [0, -1]]
v = set()
def bfs(x, y):
v.add((x,y))
q = deque([(x, y)])
while q:
x, y = q.popleft()
if (mat[x][y] == 9 and mat[x + lx][y + ly] != 1) or mat[x][y] != 1 and mat[x + lx][y + ly] == 9:
return 'yes'
for i in range(4):
dx = x + dire[i][0]
dy = y + dire[i][1]
if 0 <= dx < n and 0 <= dy < n and 0 <= dx + lx < n and 0 <= dy + ly < n and (dx,dy) not in v and mat[dx][dy] != 1 and mat[dx + lx][dy + ly] != 1:
q.append((dx, dy))
v.add((dx,dy))
return 'no'
print(bfs(a[0][0], a[0][1]))思路：普通的bfs，只是需要一次性处理两个坐标
python
from collections import deque
move = [(1,0),(-1,0),(0,1),(0,-1)]
def in_matrix(x,y):
if 0 <= x < n and 0 <= y < n and matrix[x][y] != 1:
return True
return False
def is_end(x,y):
if matrix[x][y] == 9:
return True
return False
def can(x1,y1,x2,y2):
queue = deque([(x1,y1,x2,y2)])
visited = set()
while queue:
x,y,xx,yy = queue.popleft()
visited.add((x,y,xx,yy))
for t in range(4):
dx, dy = move[t]
nx,ny,nxx,nyy = x + dx,y + dy,xx + dx,yy + dy
if in_matrix(nx,ny) and in_matrix(nxx,nyy) and (nx,ny,nxx,nyy) not in visited:
queue.append((nx,ny,nxx,nyy))
if is_end(nx,ny) or is_end(nxx,nyy):
return 'yes'
return 'no'
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
start = []
for i in range(n):
for j in range(n):
if matrix[i][j] == 5:
start.append((i,j))
for t in range(4):
dx,dy = move[t]
ni,nj = i + dx,j +dy
if in_matrix(ni,nj) and matrix[ni][nj] == 5:
start.append((ni,nj))
break
break
result = can(start[0][0],start[0][1],start[1][0],start[1][1])
print(result)1*2的人只记录其中一个位置即可，另一个位置只在判断能否移动时才发挥作用
python
from collections import deque
def chk():
for i in range(n):
for j in range(n):
if a[i][j] == 5:
for nx, ny in directions:
tx, ty = i + nx, j + ny
if 0 <= tx < n and 0 <= ty < n and a[tx][ty] == 5:
return i, j, nx, ny
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
sx, sy, adjustx, adjusty = chk()
flag = [[False] * n for _ in range(n)]
flag[sx][sy] = True
q = deque([(sx, sy)])
while q:
x, y = q.popleft()
if a[x][y] == 9 or a[x + adjustx][y + adjusty] == 9:
print("yes")
exit(0)
for nx, ny in directions:
tx, ty = x + nx, y + ny
tx2, ty2 = tx + adjustx, ty + adjusty
if 0 <= tx < n and 0 <= ty < n and 0 <= tx2 < n and 0 <= ty2 < n and\
not flag[tx][ty] and a[tx][ty] != 1 and a[tx2][ty2] != 1:
flag[tx][ty] = True
q.append((tx, ty))
print("no")