广搜BFS 做题记录(python)
2021-06-07 15:04
标签：加油 color img 使用 关于 维护 hide ret import POJ百练 4116 拯救行动 【有序队列】 1.此题存在"慢路"（有守卫的位置）与"快路"，遇到"慢路"需要消耗多倍时间/资源。故需要给类加一个是否"可直接判断"累减属性，对于"慢路"，每次访问都减一，直到该属性转变为"可判断"，此后与正常通路点一致； 2.关于python题解版本，参考hzw大佬的代码，发现POJ上使用一维无限延伸列表+维护头尾指针构造的队列可以过（耗时不到4000ms），但使用collections库自带的双向队列一定会超时（>10000ms）。不知是什么原因，可能和评测程序环境、调用库函数的时间成本有关。总之，之后在题目不做要求时可以多考虑直接用列表构造队列。 参考代码1（hzw大佬）： 参考代码2（在hzw大佬版本上、根据个人习惯的调整）： 参考代码3（deque库版本，POJ超时，仅供思路参考）： 继续加油！ 广搜BFS 做题记录(python) 标签：加油 color img 使用 关于 维护 hide ret import 原文地址：https://www.cnblogs.com/Song-Meow/p/14584149.html
a = [‘‘] * 200
xx = [0, 0, 1, -1]
yy = [-1, 1, 0, 0]
qx = [0] * 80000
qy = [0] * 80000
g = [0] * 80000
dis = [0] * 80000
mp = []
def bfs(bx, by):
head = 0
tail = 1
qx[0] = bx
qy[0] = by
while head != tail:
x, y, st, d = qx[head], qy[head], g[head], dis[head]
head = head + 1
if st == 1:
qx[tail] = x
qy[tail] = y
dis[tail] = d + 1
g[tail] = 0
tail = tail + 1
continue
for i in range(4):
tx = x + xx[i]
ty = y + yy[i]
if tx or ty or tx >= n or ty >= m or a[tx][ty] == ‘#‘:
continue
if mp[tx][ty] == 0:
if a[tx][ty] == ‘a‘:
return d + 1
mp[tx][ty] = 1
qx[tail] = tx
qy[tail] = ty
g[tail] = (a[tx][ty] == ‘x‘)
dis[tail] = d + 1
tail = tail + 1
return -1
t = int(input())
for test in range(t):
mp.clear()
n, m = map(int, input().split())
for i in range(n):
mp.append([0] * 200)
a[i] = input()
for j in range(m):
if(a[i][j] == ‘r‘):
bx, by = i, j
ans = bfs(bx, by)
if ans == -1:
print(‘Impossible‘)
else:
print(ans)
maze = ["" for i in range(200)]
dirx = [0,0,1,-1]
diry = [-1,1,0,0]
xseq = [0 for i in range(80000)]
yseq = [0 for i in range(80000)]
gd = [0 for i in range(80000)]
stp = [0 for i in range(80000)]
vis = []
n = 0
m = 0
def bfs(sx,sy):
global maze,dirx,diry,xseq,yseq,gd,stp,vis,n,m
hp = 0
tp = 1
xseq[0],yseq[0] = sx,sy
while hp != tp:
x,y,block,step = xseq[hp], yseq[hp], gd[hp], stp[hp]
hp += 1
if block == 1:
xseq[tp] = x
yseq[tp] = y
stp[tp] = step + 1
gd[tp] = 0
tp += 1
continue
for i in range(4):
tx = x + dirx[i]
ty = y + diry[i]
if (txor tyor tx>=n or ty>=m or vis[tx][ty] == 1 or maze[tx][ty] == "#"):
continue
if maze[tx][ty] == "a":
print(step+1)
return
if maze[tx][ty] == "x":
gd[tp] = 1
else:
gd[tp] = 0
xseq[tp],yseq[tp] = tx,ty
vis[tx][ty] = 1
stp[tp] = step+1
tp += 1
print("Impossible")
return
def solu():
global maze,vis,n,m
k = int(input())
for i in range(k):
vis.clear()
rget = False
n,m = map(int, input().split())
for j in range(n):
vis.append([0 for i in range(200)])
maze[j] = input()
if rget:
continue
for r in range(m):
if maze[j][r] == "r":
sx,sy = j,r
rget = True
bfs(sx,sy)
solu()
import collections
class pt():
def __init__(self,x_,y_,step_,gd_):
self.x = x_
self.y = y_
self.step = step_
self.gd = gd_
maze = ["" for i in range(205)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
vis = []
n,m = 0, 0
def bfs(sx,sy):
global maze,vis,n,m
q = collections.deque()
q.append(pt(sx,sy,0,0))
while len(q) > 0:
ptmp = q.popleft()
if ptmp.gd == 1:
q.append(pt(ptmp.x, ptmp.y, ptmp.step+1, 0))
continue
for j in range(4):
tx = ptmp.x + dx[j]
ty = ptmp.y + dy[j]
if (txor tyor tx>=n or ty>=m or vis[tx][ty]==1 or maze[tx][ty]=="#"):
continue
if maze[tx][ty] == "a":
print(ptmp.step+1)
return
if maze[tx][ty] == "x":
q.append(pt(tx,ty,ptmp.step+1,1))
else:
q.append(pt(tx,ty,ptmp.step+1,0))
print("Impossible")
return
def solu():
global maze,vis,n,m
k = int(input())
for kk in range(k):
rget = False
vis.clear()
n,m = map(int,input().split())
for i in range(n):
maze[i] = input()
vis.append([0 for i in range(205)])
if not rget:
for j in range(m):
if maze[i][j] == "r":
sx_,sy_ = i,j
rget = True
bfs(sx_,sy_)
return
solu()