#770597 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	titan23
提出日時	2022-06-12 16:23:26
言語	PyPy3 (7.3.15)
結果	AC
実行時間	485 ms / 2,000 ms
コード長	5,460 bytes
コンパイル時間	235 ms
実行使用メモリ	102,816 KB
スコア	0
平均クエリ数	1000.18
最終ジャッジ日時	2022-06-12 16:24:15
合計ジャッジ時間	47,665 ms
ジャッジサーバーID （参考情報）	judge10 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	425 ms 102,356 KB
testcase_01	AC	419 ms 102,168 KB
testcase_02	AC	473 ms 102,616 KB
testcase_03	AC	448 ms 100,924 KB
testcase_04	AC	447 ms 102,084 KB
testcase_05	AC	374 ms 101,072 KB
testcase_06	AC	388 ms 102,640 KB
testcase_07	AC	459 ms 102,644 KB
testcase_08	AC	375 ms 101,884 KB
testcase_09	AC	423 ms 100,604 KB
testcase_10	AC	408 ms 101,176 KB
testcase_11	AC	434 ms 101,140 KB
testcase_12	AC	416 ms 101,392 KB
testcase_13	AC	407 ms 102,236 KB
testcase_14	AC	381 ms 101,596 KB
testcase_15	AC	401 ms 101,604 KB
testcase_16	AC	416 ms 101,092 KB
testcase_17	AC	462 ms 102,356 KB
testcase_18	AC	367 ms 100,804 KB
testcase_19	AC	404 ms 100,872 KB
testcase_20	AC	425 ms 102,080 KB
testcase_21	AC	430 ms 101,336 KB
testcase_22	AC	414 ms 102,756 KB
testcase_23	AC	435 ms 102,332 KB
testcase_24	AC	407 ms 101,688 KB
testcase_25	AC	426 ms 101,988 KB
testcase_26	AC	303 ms 101,388 KB
testcase_27	AC	415 ms 101,732 KB
testcase_28	AC	417 ms 100,464 KB
testcase_29	AC	382 ms 101,432 KB
testcase_30	AC	424 ms 101,256 KB
testcase_31	AC	388 ms 101,252 KB
testcase_32	AC	363 ms 100,396 KB
testcase_33	AC	416 ms 102,176 KB
testcase_34	AC	425 ms 101,588 KB
testcase_35	AC	417 ms 102,364 KB
testcase_36	AC	410 ms 101,656 KB
testcase_37	AC	359 ms 100,836 KB
testcase_38	AC	360 ms 101,268 KB
testcase_39	AC	376 ms 101,896 KB
testcase_40	AC	420 ms 101,856 KB
testcase_41	AC	448 ms 101,656 KB
testcase_42	AC	415 ms 101,284 KB
testcase_43	AC	380 ms 101,876 KB
testcase_44	AC	450 ms 102,572 KB
testcase_45	AC	414 ms 102,192 KB
testcase_46	AC	363 ms 100,336 KB
testcase_47	AC	434 ms 101,896 KB
testcase_48	AC	395 ms 100,920 KB
testcase_49	AC	351 ms 101,372 KB
testcase_50	AC	448 ms 102,104 KB
testcase_51	AC	426 ms 101,284 KB
testcase_52	AC	439 ms 101,540 KB
testcase_53	AC	415 ms 101,968 KB
testcase_54	AC	437 ms 101,264 KB
testcase_55	AC	409 ms 101,356 KB
testcase_56	AC	412 ms 100,508 KB
testcase_57	AC	412 ms 101,016 KB
testcase_58	AC	426 ms 101,900 KB
testcase_59	AC	433 ms 101,612 KB
testcase_60	AC	462 ms 102,500 KB
testcase_61	AC	485 ms 101,188 KB
testcase_62	AC	413 ms 102,124 KB
testcase_63	AC	407 ms 102,816 KB
testcase_64	AC	408 ms 101,188 KB
testcase_65	AC	433 ms 101,964 KB
testcase_66	AC	433 ms 101,048 KB
testcase_67	AC	362 ms 101,176 KB
testcase_68	AC	408 ms 102,312 KB
testcase_69	AC	441 ms 101,556 KB
testcase_70	AC	442 ms 102,052 KB
testcase_71	AC	376 ms 100,548 KB
testcase_72	AC	411 ms 102,404 KB
testcase_73	AC	420 ms 101,372 KB
testcase_74	AC	425 ms 101,980 KB
testcase_75	AC	402 ms 101,116 KB
testcase_76	AC	405 ms 101,892 KB
testcase_77	AC	376 ms 100,612 KB
testcase_78	AC	406 ms 101,928 KB
testcase_79	AC	327 ms 100,140 KB
testcase_80	AC	430 ms 101,608 KB
testcase_81	AC	429 ms 101,760 KB
testcase_82	AC	392 ms 102,292 KB
testcase_83	AC	396 ms 101,968 KB
testcase_84	AC	438 ms 102,500 KB
testcase_85	AC	348 ms 101,472 KB
testcase_86	AC	422 ms 102,748 KB
testcase_87	AC	392 ms 100,572 KB
testcase_88	AC	377 ms 101,156 KB
testcase_89	AC	387 ms 100,360 KB
testcase_90	AC	379 ms 101,036 KB
testcase_91	AC	426 ms 102,432 KB
testcase_92	AC	391 ms 100,660 KB
testcase_93	AC	430 ms 102,128 KB
testcase_94	AC	432 ms 101,120 KB
testcase_95	AC	396 ms 102,532 KB
testcase_96	AC	433 ms 102,600 KB
testcase_97	AC	374 ms 100,128 KB
testcase_98	AC	390 ms 102,228 KB
testcase_99	AC	404 ms 102,780 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 True
  elif d == 'D':
    if y < 19 and v[y][x] == 1:
      return True
  elif d == 'L':
    if x and h[y][x-1] == 1:
      return True
  elif d == 'R':
    if x < 19 and h[y][x] == 1:
      return True
  return False


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

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 can_or_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

def is_edge(y, x, d):
  if x == 0 and d == 'L':  return True
  if x == 19 and d == 'R': return True
  if y == 0 and d == 'U':  return True
  if y == 19 and d == 'D': 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()*100 < P:
          indx.append((i, j))
  gy, gx = random.choice(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()*100 > 100-P:
      continue
    if is_edge(y, x, DIRECT[i]):
      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

結果

テストケース

ソースコード