結果
問題 | No.2411 Reverse Directions |
ユーザー | ニックネーム |
提出日時 | 2023-08-11 22:33:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 1,761 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 148,608 KB |
最終ジャッジ日時 | 2024-04-29 13:36:33 |
合計ジャッジ時間 | 5,445 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
54,144 KB |
testcase_01 | AC | 47 ms
53,504 KB |
testcase_02 | AC | 46 ms
53,632 KB |
testcase_03 | AC | 46 ms
53,760 KB |
testcase_04 | AC | 49 ms
55,552 KB |
testcase_05 | AC | 45 ms
53,760 KB |
testcase_06 | AC | 48 ms
53,760 KB |
testcase_07 | AC | 168 ms
124,032 KB |
testcase_08 | AC | 46 ms
53,760 KB |
testcase_09 | AC | 45 ms
54,016 KB |
testcase_10 | AC | 248 ms
148,608 KB |
testcase_11 | AC | 46 ms
53,888 KB |
testcase_12 | AC | 264 ms
132,480 KB |
testcase_13 | AC | 48 ms
54,784 KB |
testcase_14 | AC | 125 ms
86,528 KB |
testcase_15 | AC | 71 ms
67,968 KB |
testcase_16 | AC | 93 ms
79,232 KB |
testcase_17 | AC | 134 ms
89,216 KB |
testcase_18 | AC | 78 ms
72,576 KB |
testcase_19 | AC | 47 ms
54,016 KB |
testcase_20 | AC | 128 ms
88,192 KB |
testcase_21 | AC | 125 ms
89,088 KB |
testcase_22 | AC | 190 ms
108,800 KB |
testcase_23 | AC | 53 ms
55,936 KB |
testcase_24 | AC | 261 ms
129,920 KB |
testcase_25 | AC | 49 ms
54,272 KB |
testcase_26 | AC | 72 ms
71,552 KB |
testcase_27 | AC | 126 ms
85,760 KB |
testcase_28 | AC | 150 ms
96,512 KB |
testcase_29 | AC | 243 ms
128,128 KB |
testcase_30 | AC | 165 ms
102,656 KB |
testcase_31 | AC | 210 ms
115,840 KB |
ソースコード
from collections import deque h,w,k,l,r = map(int,input().split()) s = [input()+"#" for _ in range(h)]+["#"*(w+1)] if l%2==r%2: exit(print("No")) def f(x,y): d = [[10**9]*(w+1) for _ in range(h+1)] c = [[[0,0] for _ in range(w+1)] for _ in range(h+1)] d[x][y] = 0; dq = deque([(x,y)]) while dq: px,py = dq.popleft() for dx,dy in ((-1,0),(0,-1),(0,1),(1,0)): nx,ny = px+dx,py+dy if s[nx][ny]=="." and d[nx][ny]==10**9: d[nx][ny] = d[px][py]+1 c[nx][ny] = [dx,dy] dq.append((nx,ny)) return d,c def g(x,y): t1 = []; px,py = x,y while (px,py)!=(0,0): dx,dy = c1[px][py] if (dx,dy)==(-1,0): t1.append("U") if (dx,dy)==(0,-1): t1.append("L") if (dx,dy)==(0,1): t1.append("R") if (dx,dy)==(1,0): t1.append("D") px -= dx; py -= dy t2 = []; px,py = x,y while (px,py)!=(h-1,w-1): dx,dy = c2[px][py] if (dx,dy)==(-1,0): t2.append("D") if (dx,dy)==(0,-1): t2.append("R") if (dx,dy)==(0,1): t2.append("L") if (dx,dy)==(1,0): t2.append("U") px -= dx; py -= dy return "".join(t1[::-1]),"".join(t2) d1,c1 = f(0,0); d2,c2 = f(h-1,w-1) for i in range(h): for j in range(w): if d1[i][j]>l-1 or d1[i][j]%2!=(l-1)%2 or\ d2[i][j]>k-r or d2[i][j]%2!=(k-r)%2 or\ s[i][j]=="#": continue if s[i-1][j]==s[i+1][j]==".": t1,t2 = g(i,j) print("Yes") print(t1+"UD"*((k-len(t1)-len(t2))//2)+t2) exit() if s[i][j-1]==s[i][j+1]==".": t1,t2 = g(i,j) print("Yes") print(t1+"LR"*((k-len(t1)-len(t2))//2)+t2) exit() print("No")