結果

問題 No.1638 Robot Maze
ユーザー harurunharurun
提出日時 2021-06-23 14:49:01
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,666 bytes
コンパイル時間 134 ms
コンパイル使用メモリ 12,316 KB
実行使用メモリ 10,644 KB
最終ジャッジ日時 2023-10-17 02:18:57
合計ジャッジ時間 3,332 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
権限があれば一括ダウンロードができます

ソースコード

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