結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
55,168 KB
testcase_01 AC 47 ms
55,168 KB
testcase_02 AC 208 ms
96,936 KB
testcase_03 AC 208 ms
96,572 KB
testcase_04 AC 48 ms
55,296 KB
testcase_05 AC 48 ms
55,040 KB
testcase_06 AC 49 ms
55,168 KB
testcase_07 AC 47 ms
55,168 KB
testcase_08 WA -
testcase_09 AC 47 ms
55,296 KB
testcase_10 AC 48 ms
55,040 KB
testcase_11 AC 48 ms
55,296 KB
testcase_12 AC 96 ms
77,556 KB
testcase_13 AC 52 ms
56,576 KB
testcase_14 AC 91 ms
77,196 KB
testcase_15 AC 121 ms
80,964 KB
testcase_16 AC 99 ms
78,248 KB
testcase_17 AC 92 ms
77,340 KB
testcase_18 AC 106 ms
79,524 KB
testcase_19 AC 156 ms
87,668 KB
testcase_20 AC 76 ms
70,144 KB
testcase_21 AC 98 ms
82,816 KB
testcase_22 AC 89 ms
76,416 KB
testcase_23 AC 53 ms
60,928 KB
testcase_24 AC 137 ms
84,872 KB
testcase_25 AC 175 ms
90,548 KB
testcase_26 AC 97 ms
77,764 KB
testcase_27 AC 139 ms
84,272 KB
testcase_28 AC 91 ms
77,568 KB
testcase_29 AC 67 ms
67,840 KB
testcase_30 AC 105 ms
79,528 KB
testcase_31 AC 106 ms
79,392 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:
    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