結果

問題 No.1638 Robot Maze
コンテスト
ユーザー harurun
提出日時 2021-06-23 14:49:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,666 bytes
コンパイル時間 86 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-09-17 00:53:20
合計ジャッジ時間 2,648 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

class dijkstra:
  def __init__(self,V):
    self.INF=float("inf")
    self.G=[[] for _ in [0]*V]
    self.V=V
    return
  
  def add1(self,s,t,v):
    self.G[s].append([t,v])
    return
  
  def add2(self,s,t,v):
    self.G[s].append([t,v])
    self.G[t].append([s,v])
    return

  def run(self,s):
    from heapq import heapify,heappop,heappush
    ret=[self.INF]*self.V
    que=[]
    heapify(que)
    ret[s]=0
    heappush(que,(0,s))
    while que:
      p=heappop(que)
      v=p[1]
      if ret[v]<p[0]:
        continue
      for i in range(len(self.G[v])):
        e=self.G[v][i]   
        if ret[e[0]]>ret[v]+e[1]:
          ret[e[0]]=ret[v]+e[1]
          heappush(que,(ret[e[0]],e[0]))
    return ret
  
  def pop_back(self,x):
    self.G[x].pop()
    return
  
  def size(self,x):
    return len(self.G[x])

from sys import stdin
pin=stdin.readline
def main():
  ans=float("inf")
  H,W=map(int,pin().split())
  U,D,R,L,K=map(int,pin().split())
  co=(U+1)*(D+1)*(R+1)*(L+1)
  C=[]
  B=[]
  range_W=range(W)
  for i in range(H):
    C.append(list(pin().rstrip()))
    for j in range_W:
      if C[i][j]=="@":
        B.append((i,j))
    C[-1].append("#")
  C.append(["#"]*W)
  xs,ys,xt,yt=map(int,pin().split())
  xs-=1
  ys-=1
  xt-=1
  yt-=1
  V=H*W
  ijk=dijkstra(V)
  ijk_add1=ijk.add1
  for i in range(H):
    for j in range_W:
      if C[i][j]=="#":
        continue
      if C[i+1][j]==".":
        ijk_add1(W*i+j,W*(i+1)+j,D)
        ijk_add1(W*(i+1)+j,W*i+j,U)
      if C[i][j+1]==".":
        ijk_add1(W*i+j,W*i+j+1,R)
        ijk_add1(W*i+j+1,W*i+j,L)
  defa=[]
  range_V=range(V)
  defa_append=defa.append
  for i in range_V:
    defa_append(ijk.size(i))
  cnt=len(B)
  m=pow(2,cnt)
  range_cnt=range(cnt)
  ijk_pop_back=ijk.pop_back
  for i in range(m):
    u=[]
    for j in range_cnt:
      if (i>>j)&1:
        x=B[j][0]
        y=B[j][1]
        u.append((x,y))
        C[x][y]="."
    for j in range_cnt:
      if (i>>j)&1:
        x=B[j][0]
        y=B[j][1]
        if C[x+1][y]==".":
          ijk_add1(W*x+y,W*(x+1)+y,D)
          ijk_add1(W*(x+1)+y,W*x+y,U)
        if C[x][y+1]==".":
          ijk_add1(W*x+y,W*x+y+1,R)
          ijk_add1(W*x+y+1,W*x+y,L)
        if x>0 and C[x-1][y]==".":
          ijk_add1(W*x+y,W*(x-1)+y,U)
          ijk_add1(W*(x-1)+y,W*x+y,D)
        if y>0 and C[x][y-1]==".":
          ijk_add1(W*x+y,W*x+y-1,L)
          ijk_add1(W*x+y-1,W*x+y,R)
    d=ijk.run(W*xs+ys)
    ans=min(ans,d[W*xt+yt]+len(u)*co)
    for i in range_V:
      while ijk.size(i)>defa[i]:
        ijk_pop_back(i)
    for j in u:
      C[j[0]][j[1]]="@"

  if ans<=K:
    print("Yes")
  else:
    print("No")
  return

main()
0