結果

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

ソースコード

diff # 

def main(h,w,x):
  # 上下に振りながら右に行く
  # 壁にぶつかるまでは下または上に行く。ぶつかったときのみ右に行く
  mat=[["#"]*w for _ in range(h)]
  for i in range(0,h,2):
    for j in range(0,w,2):
      mat[i][j]="x"
  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]="."
  if seen[-1][-1]==x:return mat

  # 左右に振りながら上に行く
  # 壁にぶつかるまでは右または左に行く。ぶつかったときのみ下に行く
  mat=[["#"]*w for _ in range(h)]
  for i in range(0,h,2):
    for j in range(0,w,2):
      mat[i][j]="x"
  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]]

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