結果
問題 | No.1434 Make Maze |
ユーザー | chineristAC |
提出日時 | 2021-01-10 16:36:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 8,897 bytes |
コンパイル時間 | 477 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 95,080 KB |
最終ジャッジ日時 | 2024-11-24 21:36:13 |
合計ジャッジ時間 | 6,502 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
H,W,X = map(int,input().split())h = (H+1)//2w = (W+1)//2if not 2*h+2*w-4<=X<=2*h*w-2:exit(print(-1))diff = X - (2*h+2*w-4)if diff%4!=0:exit(print(-1))if w%2==1:ans = [["." for j in range(W)] for i in range(H)]pos = (0,0)rest_dist = Xans[0][0] = "T"while pos!=(H-1,W-1):x,y = posif rest_dist != (H-1-x) + (W-1-y):if x==0:if (y//2)%2==1:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)elif x==H-1:if (y//2)%2==0:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)elif (y//2)%2==0:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)rest_dist -= 2else:while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)while pos[0]!=H-1:x,y = posans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)stack = [(i,j) for i in range(H) for j in range(W) if ans[i][j]=="T" and i%2==0 and j%2==0]while stack:x,y = stack.pop()if x+2<=H-1 and ans[x+2][y]!="T":ans[x+2][y] = "T"ans[x+1][y] = "T"stack.append((x+2,y))if 2<=x and ans[x-2][y]!="T":ans[x-2][y] = "T"ans[x-1][y] = "T"stack.append((x-2,y))if y+2<=W-1 and ans[x][y+2]!="T":ans[x][y+2] = "T"ans[x][y+1] = "T"stack.append((x,y+2))if 2<=y and ans[x][y-2]!="T":ans[x][y-2] = "T"ans[x][y-1] = "T"stack.append((x,y-2))for i in range(H):for j in range(W):if ans[i][j]=="T":ans[i][j]="."else:ans[i][j]="#"print("".join(ans[i]))elif h%2==1:H,W = W,Hh,w = w,hans = [["." for j in range(W)] for i in range(H)]pos = (0,0)rest_dist = Xans[0][0] = "T"while pos!=(H-1,W-1):x,y = posif rest_dist != (H-1-x) + (W-1-y):if x==0:if (y//2)%2==1:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)elif x==H-1:if (y//2)%2==0:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)elif (y//2)%2==0:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)rest_dist -= 2else:while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)while pos[0]!=H-1:x,y = posans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)stack = [(i,j) for i in range(H) for j in range(W) if ans[i][j]=="T" and i%2==0 and j%2==0]while stack:x,y = stack.pop()if x+2<=H-1 and ans[x+2][y]!="T":ans[x+2][y] = "T"ans[x+1][y] = "T"stack.append((x+2,y))if 2<=x and ans[x-2][y]!="T":ans[x-2][y] = "T"ans[x-1][y] = "T"stack.append((x-2,y))if y+2<=W-1 and ans[x][y+2]!="T":ans[x][y+2] = "T"ans[x][y+1] = "T"stack.append((x,y+2))if 2<=y and ans[x][y-2]!="T":ans[x][y-2] = "T"ans[x][y-1] = "T"stack.append((x,y-2))for i in range(H):for j in range(W):if ans[i][j]=="T":ans[i][j]="."else:ans[i][j]="#"rev = [[ans[j][i] for j in range(H)] for i in range(W)]for i in range(W):print("".join(rev[i]))else:ans = [["." for j in range(W)] for i in range(H)]pos = (0,0)rest_dist = Xans[0][0] = "T"while pos!=(H-1,W-1):x,y = posif rest_dist != (H-1-x) + (W-1-y):if y==W-3:if (x//2)%2==0:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)elif y==W-1:if (x//2)%2==0:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)else:ans[x][y-1] = "T"ans[x][y-2] = "T"pos = (x,y-2)else:if x==0:if (y//2)%2==1:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)elif x==H-1:if (y//2)%2==0:ans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)elif (y//2)%2==0:ans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)else:ans[x-1][y] = "T"ans[x-2][y] = "T"pos = (x-2,y)rest_dist -= 2else:if y==W-3:if (x//2)%2==0:while pos[0]!=H-1:x,y = posans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:while pos[0]!=H-1:x,y = posans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)elif y==W-1:while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)else:while pos[1]!=W-1:x,y = posans[x][y+1] = "T"ans[x][y+2] = "T"pos = (x,y+2)while pos[0]!=H-1:x,y = posans[x+1][y] = "T"ans[x+2][y] = "T"pos = (x+2,y)stack = [(i,j) for i in range(H) for j in range(W) if ans[i][j]=="T" and i%2==0 and j%2==0]while stack:x,y = stack.pop()if x+2<=H-1 and ans[x+2][y]!="T":ans[x+2][y] = "T"ans[x+1][y] = "T"stack.append((x+2,y))if 2<=x and ans[x-2][y]!="T":ans[x-2][y] = "T"ans[x-1][y] = "T"stack.append((x-2,y))if y+2<=W-1 and ans[x][y+2]!="T":ans[x][y+2] = "T"ans[x][y+1] = "T"stack.append((x,y+2))if 2<=y and ans[x][y-2]!="T":ans[x][y-2] = "T"ans[x][y-1] = "T"stack.append((x,y-2))for i in range(H):for j in range(W):if ans[i][j]=="T":ans[i][j]="."else:ans[i][j]="#"print("".join(ans[i]))