結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 2022-06-12 15:01:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 3,967 bytes |
コンパイル時間 | 410 ms |
実行使用メモリ | 100,448 KB |
スコア | 0 |
平均クエリ数 | 992.00 |
最終ジャッジ日時 | 2022-06-12 15:02:22 |
合計ジャッジ時間 | 34,974 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
import sysimport mathfrom bisect import bisect_right, bisect_leftfrom itertools import *from collections import *from heapq import heapify, heappush, heappopinf = float('inf')# mod = 1000000007# mod = 998244353input = lambda: sys.stdin.readline().rstrip()def error(*args, sep=' ', end='\n'):print(*args, sep=sep, end=end, file=sys.stderr)# sys.setrecursionlimit(10**6)import randomrandom.seed = 148##################def can_move(x, y, d):if d == 'U':if y and v[y-1][x] == 0:return 1elif d == 'D':if y < 19 and v[y][x] == 0:return 1elif d == 'L':if x and h[y][x-1] == 0:return 1elif d == 'R':if x < 19 and h[y][x] == 0:return 1return 0def cannot_move(x, y, d):if d == 'U':if y and v[y-1][x] == 1:return 1elif d == 'D':if y < 19 and v[y][x] == 1:return 1elif d == 'L':if x and h[y][x-1] == 1:return 1elif d == 'R':if x < 19 and h[y][x] == 1:return 1return 0def change_yx(y, x, d):if d == 'U': y -= 1if d == 'D': y += 1if d == 'L': x -= 1if d == 'R': x += 1return (y, x)def wall_nasi(res):dq = deque(res)nowy, nowx = 0, 0while dq:d = dq.popleft()move(nowx, nowy, d)nowy, nowx = change_yx(nowy, nowx, d)def move(x, y, d):if d == 'U':v[y-1][x] = 0if d == 'D':v[y][x] = 0if d == 'L':h[y][x-1] = 0if d == 'R':h[y][x] = 0def wall_ari(res):dq = deque(res)nowy, nowx = 0, 0while dq:d = dq.popleft()if cannot_move(nowx, nowy, d):move1(nowx, nowy, d)breaknowy, nowx = change_yx(nowy, nowx, d)def move1(x, y, d):if d == 'U':v[y-1][x] = 1if d == 'D':v[y][x] = 1if d == 'L':h[y][x-1] = 1if d == 'R':h[y][x] = 1H, W, P = map(int, input().split())h = [[-1]*20 for _ in range(20)]v = [[-1]*20 for _ in range(20)]DIRECT = ['U', 'D', 'L', 'R']dx = [0, 0, -1, 1]dy = [1, -1, 0, 0]def bfs(si, sj):dist = [[-1]*20 for _ in range(20)]dq = deque([(si, sj)])dist[si][sj] = 0while dq:nowy, nowx = dq.popleft()d = dist[nowy][nowx] + 1if can_move(nowx, nowy, 'D') and dist[nowy+1][nowx] == -1:dq.append((nowy+1, nowx))dist[nowy+1][nowx] = dif can_move(nowx, nowy, 'U') and dist[nowy-1][nowx] == -1:dq.append((nowy-1, nowx))dist[nowy-1][nowx] = dif can_move(nowx, nowy, 'R') and dist[nowy][nowx+1] == -1:dq.append((nowy, nowx+1))dist[nowy][nowx+1] = dif can_move(nowx, nowy, 'L') and dist[nowy][nowx-1] == -1:dq.append((nowy, nowx-1))dist[nowy][nowx-1] = dreturn distdef get_root(dist, nowy, nowx):root = []while True:d = dist[nowy][nowx]if d == 0:breakif nowy+1 < 20 and v[nowy][nowx] == 0 and dist[nowy+1][nowx] == d-1:root.append('U')nowy += 1elif nowy-1 >= 0 and v[nowy-1][nowx] == 0 and dist[nowy-1][nowx] == d-1:root.append('D')nowy -= 1elif nowx+1 < 20 and h[nowy][nowx] == 0 and dist[nowy][nowx+1] == d-1:root.append('L')nowx += 1elif nowx-1 >= 0 and h[nowy][nowx-1] == 0 and dist[nowy][nowx-1] == d-1:root.append('R')nowx -= 1return list(reversed(root))breakflag = Falseok = []trynum = 0while trynum < 990:dist = bfs(0, 0)# solve?if dist[19][19] != -1:print(get_root(dist, 19, 19), flush=True)input()break# searchindx = []for i in range(20):for j in range(20):if dist[i][j] != -1:indx.append((i, j))gy, gx = random.choice(indx)ans = get_root(dist, gy, gx)# error(*dist, sep='\n')for i in range(4):res = ans[:]res.append(DIRECT[i])pred = len(res)print(''.join(res), flush=True)trynum += 1resnum = int(input())if resnum == -1:breakflag = Truebreakif pred == resnum:wall_nasi(res)else:wall_ari(res)if breakflag:break