結果
問題 | No.2411 Reverse Directions |
ユーザー |
|
提出日時 | 2023-08-11 23:14:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 3,322 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 103,212 KB |
最終ジャッジ日時 | 2024-11-18 18:33:28 |
合計ジャッジ時間 | 4,308 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys # sys.setrecursionlimit(5*10**5) input = sys.stdin.readline from collections import defaultdict, deque, Counter from heapq import heappop, heappush from bisect import bisect_left, bisect_right from math import gcd h,w,k,l,r = map(int,input().split()) if (r-l + 1) % 2 != 0: print("No") exit() s = [input().rstrip() for i in range(h)] dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y): que = deque([x*w+y]) depth = [-1]*(w*h) depth[x*w+y] = 0 pre = [-1]*(h*w) while que: crr= que.popleft() x,y = crr//w, crr%w for i in range(4): nx = x+dx[i] ny = y+dy[i] nxt = nx*w+ny if not(0<=nx<h and 0<=ny<w): continue if s[nx][ny] == "#": continue if depth[nxt] == -1: depth[nxt] = depth[crr] + 1 pre[nxt] = crr que.append(nxt) return depth,pre cnt = l-1 + k-r d1,p1 = bfs(0,0) d2,p2 = bfs(h-1,w-1) mid = [] mpos = () for i in range(h): for j in range(w): pos = i*w+j ok = 1 if d1[pos] == -1 or d2[pos] == -1: continue ok &= d1[pos] % 2 == (l-1)%2 ok &= d2[pos] % 2 == (k-r)%2 ok &= d1[pos] <= (l-1) ok &= d2[pos] <= (k-r) if not ok: continue if i != 0 and i != h-1 and s[i+1][j] == "." and s[i-1][j] == ".": mid = ["UD"]*((r-l+1)//2) mpos = i*w+j if j != 0 and j != w-1 and s[i][j-1] == "." and s[i][j+1] == ".": mid = ["LR"]*((r-l+1)//2) mpos = i*w+j if mid:break if mid:break if not mid: print("No") exit() pre = [] now = mpos while now != 0: now = p1[now] if now == -1: break pre.append(now) pre = pre[::-1] pre.append(mpos) suf = [mpos] now = mpos while now != (h-1)*w+w-1: now = p2[now] if now == -1: break suf.append(now) anspre = [] anssuf = [] for i in range(1,len(pre)): cx,cy = pre[i]//w, pre[i]%w px,py = pre[i-1]//w, pre[i-1]%w if cx == px + 1: anspre.append("D") if cx == px - 1: anspre.append("U") if cy == py + 1: anspre.append("R") if cy == py - 1: anspre.append("L") for i in range(1,len(suf)): cx,cy = suf[i]//w, suf[i]%w px,py = suf[i-1]//w, suf[i-1]%w if cx == px + 1: anssuf.append("D") if cx == px - 1: anssuf.append("U") if cy == py + 1: anssuf.append("R") if cy == py - 1: anssuf.append("L") if len(anspre) <= l - 1: if anspre: dif = l-1-len(anspre) if anspre[0] == "R": tmp = ["RL"]*(dif // 2) if anspre[0] == "D": tmp = ["DU"]*(dif // 2) anspre = tmp + anspre else: dif = l-1 if s[0][1]: tmp = ["RL"]*(dif // 2) else: tmp = ["DU"]*(dif // 2) anssuf = tmp if len(anssuf) <= k-r: if anssuf: dif = k-r-len(anssuf) if anssuf[-1] == "D": tmp = ["UD"]*(dif // 2) else: tmp = ["LR"]*(dif // 2) anssuf = anssuf + tmp else: dif = k-r if s[-1][-2]: tmp = ["LR"]*(dif // 2) else: tmp = ["UD"]*(dif // 2) anssuf = tmp ans = anspre + mid + anssuf print('Yes') print("".join(ans))