#770535 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	titan23
提出日時	2022-06-12 15:48:56
言語	PyPy3 (7.3.15)
結果	AC
実行時間	462 ms / 2,000 ms
コード長	5,094 bytes
コンパイル時間	703 ms
実行使用メモリ	103,060 KB
スコア	3,833
平均クエリ数	961.77
最終ジャッジ日時	2022-06-12 15:50:03
合計ジャッジ時間	47,129 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	420 ms 101,228 KB
testcase_01	AC	442 ms 100,940 KB
testcase_02	AC	446 ms 102,324 KB
testcase_03	AC	397 ms 101,344 KB
testcase_04	AC	415 ms 101,112 KB
testcase_05	AC	408 ms 101,984 KB
testcase_06	AC	403 ms 101,420 KB
testcase_07	AC	419 ms 101,480 KB
testcase_08	AC	399 ms 102,332 KB
testcase_09	AC	424 ms 101,456 KB
testcase_10	AC	405 ms 101,204 KB
testcase_11	AC	408 ms 102,408 KB
testcase_12	AC	427 ms 101,864 KB
testcase_13	AC	416 ms 100,652 KB
testcase_14	AC	394 ms 101,248 KB
testcase_15	AC	458 ms 101,480 KB
testcase_16	AC	418 ms 101,388 KB
testcase_17	AC	412 ms 101,428 KB
testcase_18	AC	386 ms 101,892 KB
testcase_19	AC	440 ms 101,968 KB
testcase_20	AC	368 ms 101,380 KB
testcase_21	AC	441 ms 102,908 KB
testcase_22	AC	457 ms 103,060 KB
testcase_23	AC	416 ms 100,744 KB
testcase_24	AC	443 ms 102,104 KB
testcase_25	AC	426 ms 101,904 KB
testcase_26	AC	334 ms 100,676 KB
testcase_27	AC	412 ms 101,568 KB
testcase_28	AC	440 ms 101,724 KB
testcase_29	AC	406 ms 101,632 KB
testcase_30	AC	348 ms 100,856 KB
testcase_31	AC	384 ms 102,052 KB
testcase_32	AC	412 ms 101,428 KB
testcase_33	AC	447 ms 101,260 KB
testcase_34	AC	450 ms 100,828 KB
testcase_35	AC	425 ms 101,556 KB
testcase_36	AC	414 ms 101,084 KB
testcase_37	AC	403 ms 100,796 KB
testcase_38	AC	450 ms 100,440 KB
testcase_39	AC	432 ms 100,456 KB
testcase_40	AC	282 ms 99,328 KB
testcase_41	AC	415 ms 102,248 KB
testcase_42	AC	422 ms 101,288 KB
testcase_43	AC	435 ms 101,384 KB
testcase_44	AC	439 ms 101,104 KB
testcase_45	AC	405 ms 101,000 KB
testcase_46	AC	404 ms 101,072 KB
testcase_47	AC	431 ms 101,012 KB
testcase_48	AC	441 ms 100,540 KB
testcase_49	AC	371 ms 100,248 KB
testcase_50	AC	277 ms 99,924 KB
testcase_51	AC	407 ms 101,292 KB
testcase_52	AC	398 ms 100,924 KB
testcase_53	AC	412 ms 101,268 KB
testcase_54	AC	428 ms 101,256 KB
testcase_55	AC	442 ms 101,980 KB
testcase_56	AC	407 ms 102,804 KB
testcase_57	AC	414 ms 101,544 KB
testcase_58	AC	400 ms 101,116 KB
testcase_59	AC	407 ms 101,064 KB
testcase_60	AC	462 ms 101,968 KB
testcase_61	AC	441 ms 101,476 KB
testcase_62	AC	416 ms 101,648 KB
testcase_63	AC	441 ms 101,212 KB
testcase_64	AC	420 ms 101,544 KB
testcase_65	AC	391 ms 101,396 KB
testcase_66	AC	401 ms 101,392 KB
testcase_67	AC	410 ms 101,048 KB
testcase_68	AC	459 ms 100,996 KB
testcase_69	AC	405 ms 100,948 KB
testcase_70	AC	259 ms 100,040 KB
testcase_71	AC	427 ms 102,000 KB
testcase_72	AC	432 ms 101,368 KB
testcase_73	AC	440 ms 101,496 KB
testcase_74	AC	414 ms 100,872 KB
testcase_75	AC	414 ms 102,020 KB
testcase_76	AC	401 ms 101,408 KB
testcase_77	AC	378 ms 101,412 KB
testcase_78	AC	396 ms 101,836 KB
testcase_79	AC	348 ms 101,928 KB
testcase_80	AC	351 ms 101,704 KB
testcase_81	AC	410 ms 102,268 KB
testcase_82	AC	439 ms 100,536 KB
testcase_83	AC	415 ms 101,424 KB
testcase_84	AC	441 ms 101,000 KB
testcase_85	AC	399 ms 101,720 KB
testcase_86	AC	383 ms 101,932 KB
testcase_87	AC	407 ms 100,676 KB
testcase_88	AC	408 ms 101,752 KB
testcase_89	AC	398 ms 100,480 KB
testcase_90	AC	417 ms 101,384 KB
testcase_91	AC	438 ms 101,900 KB
testcase_92	AC	403 ms 101,436 KB
testcase_93	AC	411 ms 101,744 KB
testcase_94	AC	393 ms 100,888 KB
testcase_95	AC	412 ms 101,008 KB
testcase_96	AC	442 ms 102,064 KB
testcase_97	AC	402 ms 101,372 KB
testcase_98	AC	404 ms 101,280 KB
testcase_99	AC	397 ms 101,236 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
import math
from bisect import bisect_right, bisect_left
from itertools import *
from collections import *
from heapq import heapify, heappush, heappop
inf = float('inf')
# mod = 1000000007
# mod = 998244353
input = 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 random

random.seed = 148

H, 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 can_move(x, y, d):
  if d == 'U':
    if y and v[y-1][x] == 0:
      return 1
  elif d == 'D':
    if y < 19 and v[y][x] == 0:
      return 1
  elif d == 'L':
    if x and h[y][x-1] == 0:
      return 1
  elif d == 'R':
    if x < 19 and h[y][x] == 0:
      return 1
  return 0

def cannot_move(x, y, d):
  if d == 'U':
    if y and v[y-1][x] == 1:
      return 1
  elif d == 'D':
    if y < 19 and v[y][x] == 1:
      return 1
  elif d == 'L':
    if x and h[y][x-1] == 1:
      return 1
  elif d == 'R':
    if x < 19 and h[y][x] == 1:
      return 1
  return 0

def change_yx(y, x, d):
  if d == 'U': y -= 1
  if d == 'D': y += 1
  if d == 'L': x -= 1
  if d == 'R': x += 1
  return (y, x)

def wall_nasi(res):
  dq = deque(res)
  nowy, nowx = 0, 0
  while 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] = 0
  if d == 'D':
    v[y][x] = 0
  if d == 'L':
    h[y][x-1] = 0
  if d == 'R':
    h[y][x] = 0

def wall_ari(res):
  dq = deque(res)
  nowy, nowx = 0, 0
  while dq:
    d = dq.popleft()
    if cannot_move(nowx, nowy, d):
      move1(nowx, nowy, d)
      break
    nowy, nowx = change_yx(nowy, nowx, d)

def move1(x, y, d):
  if d == 'U':
    v[y-1][x] = 1
  if d == 'D':
    v[y][x] = 1
  if d == 'L':
    h[y][x-1] = 1
  if d == 'R':
    h[y][x] = 1

def bfs(si, sj):
  dist = [[-1]*20 for _ in range(20)]
  dq = deque([(si, sj)])
  dist[si][sj] = 0 
  while dq:
    nowy, nowx = dq.popleft()
    d = dist[nowy][nowx] + 1
    if can_move(nowx, nowy, 'D') and dist[nowy+1][nowx] == -1:
      dq.append((nowy+1, nowx))
      dist[nowy+1][nowx] = d
    if can_move(nowx, nowy, 'U') and dist[nowy-1][nowx] == -1:
      dq.append((nowy-1, nowx))
      dist[nowy-1][nowx] = d
    if can_move(nowx, nowy, 'R') and dist[nowy][nowx+1] == -1:
      dq.append((nowy, nowx+1))
      dist[nowy][nowx+1] = d
    if can_move(nowx, nowy, 'L') and dist[nowy][nowx-1] == -1:
      dq.append((nowy, nowx-1))
      dist[nowy][nowx-1] = d
  return dist
def get_root(dist, nowy, nowx):
  root = []
  while True:
    d = dist[nowy][nowx]
    if d == 0:
      break
    if   nowy+1 < 20 and v[nowy][nowx] == 0 and dist[nowy+1][nowx] == d-1:
      root.append('U')
      nowy += 1
    elif nowy-1 >= 0 and v[nowy-1][nowx] == 0 and dist[nowy-1][nowx] == d-1:
      root.append('D')
      nowy -= 1
    elif nowx+1 < 20 and h[nowy][nowx] == 0 and dist[nowy][nowx+1] == d-1:
      root.append('L')
      nowx += 1
    elif nowx-1 >= 0 and h[nowy][nowx-1] == 0 and dist[nowy][nowx-1] == d-1:
      root.append('R')
      nowx -= 1
  return list(reversed(root))

def get_goal(dist, nowy, nowx):
  while True:
    d = dist[nowy][nowx]
    if d == 0:
      break
    if   nowy+1 < 20 and v[nowy][nowx] == 0 and dist[nowy+1][nowx] == d-1:
      nowy += 1
    elif nowy-1 >= 0 and v[nowy-1][nowx] == 0 and dist[nowy-1][nowx] == d-1:
      nowy -= 1
    elif nowx+1 < 20 and h[nowy][nowx] == 0 and dist[nowy][nowx+1] == d-1:
      nowx += 1
    elif nowx-1 >= 0 and h[nowy][nowx-1] == 0 and dist[nowy][nowx-1] == d-1:
      nowx -= 1
  return (nowy, nowx)



def same(d1, d2):
  if d1 == 'D' and d2 == 'U': return True
  if d1 == 'U' and d2 == 'D': return True
  if d1 == 'L' and d2 == 'R': return True
  if d1 == 'R' and d2 == 'L': return True
  return False

breakflag = False
ok = []
trynum = 0
seen = set()
while trynum < 1000:
  dist = bfs(0, 0)
  indx = (0, 0)
  for i in range(20):
    for j in range(20):
      if dist[i][j] != -1:
        if (i, j) not in seen or random.random() < 0.2:
          if i+j > indx[0]+indx[1]:
            indx = (i, j)
  gy, gx = indx
  seen.add((gy, gx))
  ans = get_root(dist, gy, gx)
  # error(*dist, sep='\n')
  # error()
  # error(*h, sep='\n')
  # error()
  # error(*v, sep='\n')
  for i in range(4):
    res = ans[:]
    if res and same(res[-1], DIRECT[i]): continue
    x, y = get_goal(dist, 0, 0)
    if cannot_move(x, y, DIRECT[i]) and random.random() > 0.8:
      continue
    if x == 0 and DIRECT[i] == 'L':
      continue
    if x == 19 and DIRECT[i] == 'R':
      continue
    if y == 0 and DIRECT[i] == 'U':
      continue
    if y == 19 and DIRECT[i] == 'D':
      continue

    res.append(DIRECT[i])
    pred = len(res)
    print(''.join(res), flush=True)
    trynum += 1
    resnum = int(input())
    if resnum == -1:
      breakflag = True
      break
    if pred == resnum:
      wall_nasi(res)
    else:
      wall_ari(res)  
  if breakflag:
    break

yukicoder

結果

テストケース

ソースコード