結果

問題 No.5006 Hidden Maze
コンテスト
ユーザー brthyyjp
提出日時 2022-06-12 15:02:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 285 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 215 ms
実行使用メモリ 100,144 KB
スコア 15,806
平均クエリ数 842.11
最終ジャッジ日時 2022-06-12 15:02:54
合計ジャッジ時間 28,416 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def query(s):
    print(''.join(s), flush = True)
    v = int(input())
    if v == -1:
        exit()
    return v

dys = (0, 1, 0, -1)
dxs = (-1, 0, 1, 0)
direcs = "LDRU"
toid = {'L':0, 'D':1, 'R':2, 'U':3}

def reconst(s, l):
    y, x = 0, 0
    for i in range(l):
        dir = toid[s[i]]
        if dir == 0:
            ver[y][x] = 0
        elif dir == 1:
            hor[y+1][x] = 0
        elif dir == 2:
            ver[y][x+1] = 0
        else:
            hor[y][x] = 0
        dy, dx = dys[dir], dxs[dir]
        y, x = y+dy, x+dx
    dir = toid[s[l]]
    if dir == 0:
        ver[y][x] = 1
    elif dir == 1:
        hor[y+1][x] = 1
    elif dir == 2:
        ver[y][x+1] = 1
    else:
        hor[y][x] = 1

h, w, p = map(int, input().split())

start = 0
goal = (h-1)*w+w-1
maxT = 1000

hor = [[-1]*w for i in range(h+1)]
ver = [[-1]*(w+1) for i in range(h)]

for x in range(w):
    hor[0][x] = 1
    hor[h][x] = 1

for y in range(h):
    ver[y][0] = 1
    ver[y][w] = 1

for iter in range(maxT//2):
    q = deque([])
    q.append(0)
    prev = [-1]*(h*w)
    direction = [-1]*(h*w)
    visit = [False]*(h*w)
    visit[0] = True
    while q:
        v = q.popleft()
        y, x = divmod(v, w)
        for i in range(4):
            dy, dx = dys[i], dxs[i]
            ny = y + dy
            nx = x + dx
            if not (0 <= ny < h and 0 <= nx < w):
                continue
            if (dx==-1 and ver[y][x]!=1) or (dx==1 and ver[y][x+1] != 1) or (dy==-1 and hor[y][x]!=1) or (dy==1 and hor[y+1][x]!=1):
                nv = ny*w+nx
                if not visit[nv]:
                    q.append(nv)
                    prev[nv] = v
                    direction[nv] = i
                    visit[nv] = True
    if visit[goal]:
        cur = goal
        s = []
        while cur != -1:
            if cur != start:
                dir = direction[cur]
                s.append(direcs[dir])
            cur = prev[cur]
        s.reverse()
        v0 = query(s)
        v1 = query(s)
        reconst(s, max(v0, v1))
    else:
        s = ['D']*(h-1)+['R']*(w-1)
        v0 = query(s)
        v1 = query(s)
        reconst(s, max(v0, v1))
0