結果

問題 No.1434 Make Maze
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-08 15:35:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,742 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 104,332 KB
最終ジャッジ日時 2024-05-05 00:55:00
合計ジャッジ時間 7,997 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
55,424 KB
testcase_01 AC 49 ms
55,168 KB
testcase_02 AC 313 ms
104,328 KB
testcase_03 AC 298 ms
104,332 KB
testcase_04 AC 45 ms
55,040 KB
testcase_05 AC 42 ms
54,912 KB
testcase_06 AC 42 ms
55,040 KB
testcase_07 AC 42 ms
55,296 KB
testcase_08 WA -
testcase_09 AC 43 ms
55,040 KB
testcase_10 AC 44 ms
55,296 KB
testcase_11 AC 42 ms
55,552 KB
testcase_12 AC 105 ms
78,432 KB
testcase_13 AC 57 ms
65,024 KB
testcase_14 AC 112 ms
78,228 KB
testcase_15 AC 165 ms
83,528 KB
testcase_16 AC 113 ms
79,312 KB
testcase_17 AC 107 ms
78,088 KB
testcase_18 AC 124 ms
80,520 KB
testcase_19 AC 200 ms
92,544 KB
testcase_20 AC 78 ms
70,400 KB
testcase_21 AC 89 ms
82,688 KB
testcase_22 AC 77 ms
76,672 KB
testcase_23 AC 49 ms
60,928 KB
testcase_24 AC 171 ms
88,184 KB
testcase_25 AC 249 ms
95,372 KB
testcase_26 AC 109 ms
78,348 KB
testcase_27 AC 173 ms
87,552 KB
testcase_28 AC 101 ms
78,364 KB
testcase_29 AC 76 ms
75,136 KB
testcase_30 AC 124 ms
80,184 KB
testcase_31 AC 127 ms
79,984 KB
権限があれば一括ダウンロードができます

ソースコード

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:
    if chk(h,w,x,mat):
      for ary in mat:
        print(*ary,sep="")
    else:
      print(hoge)

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