結果

問題 No.1434 Make Maze
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-08 15:39:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,238 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 96,036 KB
最終ジャッジ日時 2024-05-05 00:58:53
合計ジャッジ時間 7,499 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
55,424 KB
testcase_01 AC 47 ms
55,296 KB
testcase_02 AC 218 ms
95,908 KB
testcase_03 AC 214 ms
96,036 KB
testcase_04 AC 47 ms
55,040 KB
testcase_05 AC 45 ms
55,200 KB
testcase_06 AC 45 ms
55,296 KB
testcase_07 AC 45 ms
55,040 KB
testcase_08 WA -
testcase_09 AC 45 ms
55,168 KB
testcase_10 AC 44 ms
55,424 KB
testcase_11 AC 44 ms
55,552 KB
testcase_12 AC 84 ms
77,332 KB
testcase_13 AC 48 ms
56,704 KB
testcase_14 AC 85 ms
77,072 KB
testcase_15 AC 119 ms
80,952 KB
testcase_16 AC 85 ms
78,228 KB
testcase_17 AC 79 ms
77,312 KB
testcase_18 AC 96 ms
79,772 KB
testcase_19 AC 142 ms
87,552 KB
testcase_20 AC 93 ms
77,508 KB
testcase_21 AC 131 ms
88,576 KB
testcase_22 AC 106 ms
80,172 KB
testcase_23 AC 53 ms
62,080 KB
testcase_24 AC 128 ms
85,136 KB
testcase_25 AC 168 ms
89,460 KB
testcase_26 AC 84 ms
77,412 KB
testcase_27 AC 129 ms
84,260 KB
testcase_28 AC 82 ms
77,952 KB
testcase_29 AC 60 ms
67,840 KB
testcase_30 AC 96 ms
79,648 KB
testcase_31 AC 95 ms
79,648 KB
権限があれば一括ダウンロードができます

ソースコード

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