結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 mymelochan
|
| 提出日時 | 2023-08-11 23:58:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,248 bytes |
| コンパイル時間 | 608 ms |
| コンパイル使用メモリ | 82,572 KB |
| 実行使用メモリ | 107,044 KB |
| 最終ジャッジ日時 | 2024-11-18 19:50:07 |
| 合計ジャッジ時間 | 6,070 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 42 ms
56,340 KB |
| testcase_01 | AC | 45 ms
56,488 KB |
| testcase_02 | AC | 41 ms
55,676 KB |
| testcase_03 | AC | 41 ms
57,160 KB |
| testcase_04 | AC | 79 ms
100,920 KB |
| testcase_05 | AC | 42 ms
55,800 KB |
| testcase_06 | AC | 40 ms
56,556 KB |
| testcase_07 | AC | 85 ms
81,416 KB |
| testcase_08 | AC | 39 ms
56,248 KB |
| testcase_09 | AC | 39 ms
56,728 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 43 ms
57,528 KB |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 65 ms
71,400 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 45 ms
55,680 KB |
| testcase_20 | WA | - |
| testcase_21 | AC | 80 ms
78,024 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 50 ms
57,088 KB |
| testcase_24 | WA | - |
| testcase_25 | AC | 48 ms
56,192 KB |
| testcase_26 | AC | 68 ms
69,828 KB |
| testcase_27 | AC | 105 ms
77,412 KB |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | AC | 133 ms
79,984 KB |
ソースコード
#############################################################
import sys
sys.setrecursionlimit(10**7)
from heapq import heappop,heappush
from collections import deque,defaultdict,Counter
from bisect import bisect_left, bisect_right
from itertools import product,combinations,permutations
from math import sin,cos
#from math import isqrt #DO NOT USE PyPy
ipt = sys.stdin.readline
iin = lambda :int(ipt())
lmin = lambda :list(map(int,ipt().split()))
inf = 1<<30
#############################################################
H,W,K,L,R = lmin()
S = [input() for _ in range(H)]
if (R-L)%2 == 0:
print("No")
exit()
costs = [[inf]*W for _ in range(H)]
costt = [[inf]*W for _ in range(H)]
costs[0][0] = 0
costt[H-1][W-1] = 0
d = [(-1,0),(0,-1),(1,0),(0,1)]
d1 = [(-1,0,"D"),(0,-1,"R"),(1,0,"U"),(0,1,"L")]
d2 = [(-1,0,"U"),(0,-1,"L"),(1,0,"D"),(0,1,"R")]
dq = deque([(0,0,0)])
while dq:
i,j,c = dq.pop()
for di,dj in d:
ni,nj = i+di,j+dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
if costs[ni][nj] != inf:
continue
costs[ni][nj] = c+1
dq.appendleft((ni,nj,c+1))
dq = deque([(H-1,W-1,0)])
while dq:
i,j,c = dq.pop()
for di,dj in d:
ni,nj = i+di,j+dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
if costt[ni][nj] != inf:
continue
costt[ni][nj] = c+1
dq.appendleft((ni,nj,c+1))
if costs[H-1][W-1] == inf:
print("No")
exit()
for i in range(H):
for j in range(W):
r1 = (i+j)%2
r2 = (L-1)%2
r3 = (K-R)%2
r4 = (H+W-i-j)%2
if r1 == r2 and r4 == r3:
if L-1 >= costs[i][j] and K-R >= costt[i][j]:
if 1 <= j < W-1 and S[i][j-1] == "." and S[i][j] == "." and S[i][j+1] == ".":
#print((i,j))
ci,cj = i,j
ans = []
while True:
#print(ci,cj)
if ci == 0 and cj == 0:
break
for di,dj,u in d1:
ni,nj = ci+di,cj+dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
if costs[ni][nj] == costs[ci][cj]-1:
ci = ni
cj = nj
ans.append(u)
break
#print(ans)
ans.reverse()
for _ in range((L-1-costs[i][j])//2):
ans.append("L")
ans.append("R")
for _ in range((R-L+1)//2):
ans.append("L")
ans.append("R")
#print(ans)
ci,cj = i,j
while True:
if ci == H-1 and cj == W-1:
break
for di,dj,u in d2:
ni,nj = ci+di,cj+dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
if costt[ni][nj] == costt[ci][cj]-1:
ci = ni
cj = nj
ans.append(u)
break
print("Yes")
print("".join(ans))
exit()
if 1 <= i < H-1 and S[i-1][j] == "." and S[i][j] == "." and S[i+1][j] == ".":
ci,cj = i,j
ans = []
while True:
if ci == 0 and cj == 0:
break
for di,dj,u in d1:
ni,nj = ci+di,cj+dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
if costs[ni][nj] == costs[ci][cj]-1:
ci = ni
cj = nj
ans.append(u)
break
ans.reverse()
for _ in range((K-R-costt[i][j])//2):
ans.append("U")
ans.append("D")
for _ in range((R-L+1)//2):
ans.append("U")
ans.append("D")
ci,cj = i,j
while True:
if ci == H-1 and cj == W-1:
break
for di,dj,u in d2:
ni,nj = ci+di,cj+dj
if 0 <= ni < H and 0 <= nj < W:
if costt[ni][nj] == costt[ci][cj]-1:
ci = ni
cj = nj
ans.append(u)
break
print("Yes")
print("".join(ans))
exit()
print("No")