結果

問題 No.1434 Make Maze
ユーザー persimmon-persimmon
提出日時 2021-06-08 15:32:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,687 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 96,304 KB
最終ジャッジ日時 2024-11-26 16:56:18
合計ジャッジ時間 7,514 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main(h,w,x):
  min_x=h+w-2
  max_x=min_x+max((h-1)*(w//4)*2,(w-1)*(h//4)*2)
  if True:#min_x <= x <= max_x and (x-min_x)%4==0:
    mat=[["#"]*w for _ in range(h)]
    for i in range(0,h,2):
      for j in range(0,w,2):
        mat[i][j]="x"
    if (h-1)*(w//4)*2>(w-1)*(h//4)*2:
      # 上下に振りながら右に行く
      # 壁にぶつかるまでは下または上に行く。ぶつかったときのみ右に行く
      seen=[[-1]*w for _ in range(h)]
      seen[0][0]=0
      for i in range(h):
        seen[i][0]=i
        mat[i][0]="."
      todo=[[i,0]]
      while todo:
        i,j=todo.pop()
        mat[i][j]="."
        if [i,j]==[h-1,w-1]:break
        if seen[i][j]+(h-i-1)+(w-j-1)==x:
          # ここからは最短距離を歩く
          # 右に行けるだけ右に行く
          while [i,j]!=[h-1,w-1]:
            if j+1<w:
              seen[i][j+1]=seen[i][j]+1
              j+=1
            else:
              seen[i+1][j]=seen[i][j]+1
              i+=1
            mat[i][j]="."
          break
        elif i+1<h and seen[i+1][j]==-1:
          # 下にいく
          seen[i+1][j]=seen[i][j]+1
          seen[i+2][j]=seen[i][j]+2
          mat[i+1][j]="."
          todo.append([i+2,j])
        elif 0<=i-1 and seen[i-1][j]==-1:
          # 上にいく
          seen[i-1][j]=seen[i][j]+1
          seen[i-2][j]=seen[i][j]+2
          mat[i-1][j]="."
          todo.append([i-2,j])
        else:
          # 右に行く
          seen[i][j+1]=seen[i][j]+1
          mat[i][j+1]="."
          seen[i][j+2]=seen[i][j]+2
          todo.append([i,j+2])
      for i in range(h):
        for j in range(w):
          if mat[i][j]=="x":
            mat[i][j]="."
            if i+1<h:mat[i+1][j]="."
            if 0<=i-1:mat[i-1][j]="."
    else:
      # 左右に振りながら上に行く
      # 壁にぶつかるまでは右または左に行く。ぶつかったときのみ下に行く
      seen=[[-1]*w for _ in range(h)]
      seen[0][0]=0
      for i in range(w):
        seen[0][i]=i
        mat[0][i]="."
      todo=[[0,i]]

      while todo:
        i,j=todo.pop()
        mat[i][j]="."
        if [i,j]==[h-1,w-1]:break
        if seen[i][j]+(h-i-1)+(w-j-1)==x:
          # ここからは最短距離を歩く
          # 下に行けるだけ下に行く
          while [i,j]!=[h-1,w-1]:
            if i+1<h:
              seen[i+1][j]=seen[i][j]+1
              i+=1
            else:
              seen[i][j+1]=seen[i][j]+1
              j+=1
            mat[i][j]="."
          break
        elif j+1<w and seen[i][j+1]==-1:
          # 右にいく
          seen[i][j+1]=seen[i][j]+1
          seen[i][j+2]=seen[i][j]+2
          mat[i][j+1]="."
          todo.append([i,j+2])
        elif 0<=j-1 and seen[i][j-1]==-1:
          # 左にいく
          seen[i][j-1]=seen[i][j]+1
          seen[i][j-2]=seen[i][j]+2
          mat[i][j-1]="."
          todo.append([i,j-2])
        else:
          # 下に行く
          seen[i+1][j]=seen[i][j]+1
          mat[i+1][j]="."
          seen[i+2][j]=seen[i][j]+2
          todo.append([i+2,j])
      for i in range(h):
        for j in range(w):
          pass
          if mat[i][j]=="x":
            mat[i][j]="."
            if j+1<w:mat[i][j+1]="."
            if 0<=j-1:mat[i][j-1]="."
    if seen[-1][-1]==x:return mat
    return [[-1]]
  else:
    return [[-1]]

def chk(h,w,x,mat):
  todo=[[0,0,-1,-1]]
  seen=[[-1]*w for _ in range(h)]
  seen[0][0]=0
  while todo:
    i,j,pi,pj=todo.pop()
    for di,dj in ((0,1),(0,-1),(1,0),(-1,0)):
      ni,nj=i+di,j+dj
      if 0<=ni<h and 0<=nj<w:
        if [ni,nj]==[pi,pj]:continue
        if mat[ni][nj]==".":
          if seen[ni][nj]==-1:
            seen[ni][nj]=seen[i][j]+1
            todo.append([ni,nj,i,j])
          elif seen[ni][nj]!=-1:
            return False
  if seen[-1][-1]!=x:
    return False
  for i in range(h):
    for j in range(w):
      if mat[i][j]=="." and seen[i][j]==-1:
        return False
  for i in range(0,h,2):
    for j in range(0,w,2):
      if mat[i][j]=="#":return False
  for i in range(1,h,2):
    for j in range(1,w,2):
      if mat[i][j]==".":return False
  
  return True

if __name__=='__main__':
  h,w,x=map(int,input().split())
  mat = main(h,w,x)
  if mat[0][0]==-1:
    print(-1)
  else:
    for ary in mat:
      print(*ary,sep="")

from random import randint
if __name__=='__main__1':
  for _ in range(1000):
    h=randint(1,10)*2+1
    w=randint(1,10)*2+1
    x=randint(h+w-2,h*w)
    ret=main(h,w,x)
    if ret[0][0]==-1:continue
    if chk(h,w,x,ret):
      continue
    else:
      print(h,w,x)
      for ary in ret:
        print("".join(ary))
      break
0