結果

問題 No.5006 Hidden Maze
ユーザー brthyyjp
提出日時 2022-06-12 15:41:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 2,370 bytes
コンパイル時間 260 ms
実行使用メモリ 100,564 KB
スコア 8,402
平均クエリ数 916.98
最終ジャッジ日時 2022-06-12 15:42:01
合計ジャッジ時間 39,772 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = 1001
cnt = 0
while cnt < maxT:
    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):
        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)
            v = query(s)
            #reconst(s, max(v0, v1))
            reconst(s, v)
            cnt += 1
        else:
            break
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0