結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 mymelochan
|
| 提出日時 | 2023-08-12 00:04:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 222 ms / 2,000 ms |
| コード長 | 5,326 bytes |
| コンパイル時間 | 642 ms |
| コンパイル使用メモリ | 82,164 KB |
| 実行使用メモリ | 113,792 KB |
| 最終ジャッジ日時 | 2024-11-18 19:54:25 |
| 合計ジャッジ時間 | 5,568 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 52 ms
55,296 KB |
| testcase_01 | AC | 52 ms
55,040 KB |
| testcase_02 | AC | 52 ms
55,296 KB |
| testcase_03 | AC | 52 ms
55,424 KB |
| testcase_04 | AC | 101 ms
99,840 KB |
| testcase_05 | AC | 54 ms
55,424 KB |
| testcase_06 | AC | 52 ms
55,296 KB |
| testcase_07 | AC | 107 ms
81,024 KB |
| testcase_08 | AC | 51 ms
55,296 KB |
| testcase_09 | AC | 51 ms
55,424 KB |
| testcase_10 | AC | 222 ms
106,496 KB |
| testcase_11 | AC | 53 ms
55,552 KB |
| testcase_12 | AC | 198 ms
98,176 KB |
| testcase_13 | AC | 55 ms
55,936 KB |
| testcase_14 | AC | 145 ms
90,112 KB |
| testcase_15 | AC | 101 ms
82,176 KB |
| testcase_16 | AC | 83 ms
70,912 KB |
| testcase_17 | AC | 137 ms
84,224 KB |
| testcase_18 | AC | 120 ms
92,288 KB |
| testcase_19 | AC | 53 ms
55,296 KB |
| testcase_20 | AC | 128 ms
78,720 KB |
| testcase_21 | AC | 103 ms
78,080 KB |
| testcase_22 | AC | 169 ms
90,496 KB |
| testcase_23 | AC | 59 ms
57,088 KB |
| testcase_24 | AC | 173 ms
83,840 KB |
| testcase_25 | AC | 54 ms
56,064 KB |
| testcase_26 | AC | 75 ms
69,632 KB |
| testcase_27 | AC | 121 ms
77,184 KB |
| testcase_28 | AC | 173 ms
106,752 KB |
| testcase_29 | AC | 213 ms
113,792 KB |
| testcase_30 | AC | 181 ms
108,416 KB |
| testcase_31 | AC | 153 ms
79,744 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+(K-R-costt[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))
print(len(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((L-1-costs[i][j])//2+(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")