結果

問題 No.1638 Robot Maze
ユーザー harurunharurun
提出日時 2021-06-24 19:57:01
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,196 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 81,816 KB
実行使用メモリ 65,956 KB
最終ジャッジ日時 2023-10-17 02:19:49
合計ジャッジ時間 4,876 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 # 

#assert
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])

class INPUT:
  def __init__(self):
    self._l=open(0).read().split()
    self._length=len(self._l)
    self._index=0
    return

  def stream(self,k=1,f=int,f2=False):
    assert(-1<k)
    if self._length==self._index or self._length-self._index<k:
      raise Exception("There is no input!")
    elif f!=str:
      if k==0:
        ret=list(map(f,self._l[self._index:]))
        self._index=self._length
        return ret
      if k==1 and not f2:
        ret=f(self._l[self._index])
        self._index+=1
        return ret
      if k==1 and f2:
        ret=[f(self._l[self._index])]
        self._index+=1
        return ret
      ret=[]
      for _ in [0]*k:
        ret.append(f(self._l[self._index]))
        self._index+=1
      return ret
    else:
      if k==0:
        ret=list(self._l[self._index:])
        self._index=self._length
        return ret
      if k==1 and not f2:
        ret=self._l[self._index]
        self._index+=1
        return ret
      if k==1 and f2:
        ret=[self._l[self._index]]
        self._index+=1
        return ret
      ret=[]
      for _ in [0]*k:
        ret.append(self._l[self._index])
        self._index+=1
      return ret
pin=INPUT().stream

"""
pin(number[default:1],f[default:int],f2[default:False])
if number==0 -> return left all
listを変数で受け取るとき、必ずlistをTrueにすること。
"""

def main():
  ans=float("inf")
  H,W,U,D,R,L,K=pin(7)
  assert(2<=H<=100)
  assert(2<=W<=100)
  assert(0<=U<=100)
  assert(0<=D<=100)
  assert(0<=R<=100)
  assert(0<=L<=100)
  assert(0<=K<=10**18)
  co=(U+1)*(D+1)*(R+1)*(L+1)
  C=[]
  B=[]
  for i in range(H):
    C.append(list(pin(1,str)))
    assert(len(C[i])==W)
    for j in range(W):
      assert(C[i][j] in [".","#","@"])
      if C[i][j]=="@":
        B.append((i,j))
    C[-1].append("#")
  assert(len(B)<=8)
  C.append(["#"]*W)
  xs,ys,xt,yt=pin(4)
  assert((xs,ys)!=(xt,yt))
  assert(1<=xs<=H)
  assert(1<=ys<=W)
  assert(1<=xt<=H)
  assert(1<=yt<=W)
  xs-=1
  ys-=1
  xt-=1
  yt-=1
  assert(C[xs][ys]==".")
  assert(C[xt][yt]==".")
  V=H*W
  ijk=dijkstra(V)
  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=[]
  for i in range(V):
    defa.append(ijk.size(i))
  cnt=len(B)
  m=pow(2,cnt)
  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