結果

問題 No.1638 Robot Maze
ユーザー harurunharurun
提出日時 2021-06-23 14:35:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 3,808 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-09-17 00:53:08
合計ジャッジ時間 2,682 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])

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)
  co=(U+1)*(D+1)*(R+1)*(L+1)
  C=[]
  B=[]
  for i in range(H):
    C.append(list(pin(1,str)))
    for j in range(W):
      if C[i][j]=="@":
        B.append((i,j))
    C[-1].append("#")
  C.append(["#"]*W)
  xs,ys,xt,yt=pin(4)
  xs-=1
  ys-=1
  xt-=1
  yt-=1
  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