#770636 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	titan23
提出日時	2022-06-12 16:52:17
言語	PyPy3 (7.3.15)
結果	AC
実行時間	451 ms / 2,000 ms
コード長	5,553 bytes
コンパイル時間	501 ms
実行使用メモリ	103,716 KB
スコア	0
平均クエリ数	1000.16
最終ジャッジ日時	2022-06-12 16:53:04
合計ジャッジ時間	46,696 ms
ジャッジサーバーID （参考情報）	judge13 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	390 ms 101,068 KB
testcase_01	AC	423 ms 102,492 KB
testcase_02	AC	395 ms 102,332 KB
testcase_03	AC	411 ms 101,004 KB
testcase_04	AC	426 ms 101,884 KB
testcase_05	AC	400 ms 101,596 KB
testcase_06	AC	410 ms 102,244 KB
testcase_07	AC	405 ms 101,360 KB
testcase_08	AC	378 ms 101,452 KB
testcase_09	AC	381 ms 101,572 KB
testcase_10	AC	424 ms 101,384 KB
testcase_11	AC	418 ms 101,688 KB
testcase_12	AC	399 ms 101,924 KB
testcase_13	AC	387 ms 101,348 KB
testcase_14	AC	414 ms 101,344 KB
testcase_15	AC	418 ms 102,104 KB
testcase_16	AC	419 ms 101,328 KB
testcase_17	AC	418 ms 102,264 KB
testcase_18	AC	381 ms 102,204 KB
testcase_19	AC	392 ms 101,168 KB
testcase_20	AC	429 ms 101,256 KB
testcase_21	AC	402 ms 101,636 KB
testcase_22	AC	418 ms 101,844 KB
testcase_23	AC	394 ms 100,856 KB
testcase_24	AC	373 ms 101,940 KB
testcase_25	AC	412 ms 101,696 KB
testcase_26	AC	296 ms 101,552 KB
testcase_27	AC	405 ms 100,828 KB
testcase_28	AC	397 ms 101,620 KB
testcase_29	AC	388 ms 101,436 KB
testcase_30	AC	451 ms 101,840 KB
testcase_31	AC	443 ms 103,716 KB
testcase_32	AC	378 ms 101,240 KB
testcase_33	AC	406 ms 102,104 KB
testcase_34	AC	412 ms 101,284 KB
testcase_35	AC	434 ms 102,068 KB
testcase_36	AC	375 ms 101,956 KB
testcase_37	AC	404 ms 102,068 KB
testcase_38	AC	400 ms 102,232 KB
testcase_39	AC	366 ms 100,852 KB
testcase_40	AC	420 ms 101,916 KB
testcase_41	AC	429 ms 102,308 KB
testcase_42	AC	380 ms 101,788 KB
testcase_43	AC	410 ms 101,488 KB
testcase_44	AC	428 ms 102,180 KB
testcase_45	AC	423 ms 101,668 KB
testcase_46	AC	408 ms 101,648 KB
testcase_47	AC	422 ms 101,904 KB
testcase_48	AC	374 ms 102,228 KB
testcase_49	AC	379 ms 102,032 KB
testcase_50	AC	429 ms 102,108 KB
testcase_51	AC	421 ms 102,868 KB
testcase_52	AC	377 ms 100,344 KB
testcase_53	AC	418 ms 101,840 KB
testcase_54	AC	399 ms 102,484 KB
testcase_55	AC	427 ms 101,856 KB
testcase_56	AC	428 ms 101,536 KB
testcase_57	AC	385 ms 102,032 KB
testcase_58	AC	404 ms 101,996 KB
testcase_59	AC	392 ms 102,092 KB
testcase_60	AC	441 ms 101,988 KB
testcase_61	AC	412 ms 101,000 KB
testcase_62	AC	428 ms 101,380 KB
testcase_63	AC	422 ms 103,232 KB
testcase_64	AC	400 ms 101,736 KB
testcase_65	AC	415 ms 102,024 KB
testcase_66	AC	397 ms 101,852 KB
testcase_67	AC	383 ms 101,872 KB
testcase_68	AC	397 ms 101,752 KB
testcase_69	AC	408 ms 101,756 KB
testcase_70	AC	425 ms 101,492 KB
testcase_71	AC	433 ms 102,916 KB
testcase_72	AC	390 ms 101,844 KB
testcase_73	AC	422 ms 100,904 KB
testcase_74	AC	390 ms 101,432 KB
testcase_75	AC	375 ms 101,300 KB
testcase_76	AC	395 ms 101,212 KB
testcase_77	AC	377 ms 102,004 KB
testcase_78	AC	399 ms 100,988 KB
testcase_79	AC	354 ms 101,284 KB
testcase_80	AC	422 ms 102,408 KB
testcase_81	AC	399 ms 101,140 KB
testcase_82	AC	393 ms 101,832 KB
testcase_83	AC	420 ms 102,660 KB
testcase_84	AC	421 ms 102,236 KB
testcase_85	AC	403 ms 101,688 KB
testcase_86	AC	423 ms 101,452 KB
testcase_87	AC	418 ms 102,432 KB
testcase_88	AC	392 ms 102,196 KB
testcase_89	AC	407 ms 101,260 KB
testcase_90	AC	420 ms 102,896 KB
testcase_91	AC	442 ms 102,648 KB
testcase_92	AC	381 ms 101,564 KB
testcase_93	AC	420 ms 102,028 KB
testcase_94	AC	412 ms 102,320 KB
testcase_95	AC	429 ms 102,252 KB
testcase_96	AC	441 ms 101,940 KB
testcase_97	AC	398 ms 101,448 KB
testcase_98	AC	398 ms 101,044 KB
testcase_99	AC	399 ms 102,200 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:
          if random.random() < 0.5:
            if i+j > indx[0]+indx[1]:
              indx = (i, j)
          else:
            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()*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

結果

テストケース

ソースコード