#770577 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	titan23
提出日時	2022-06-12 16:11:57
言語	PyPy3 (7.3.15)
結果	AC
実行時間	427 ms / 2,000 ms
コード長	5,467 bytes
コンパイル時間	278 ms
実行使用メモリ	102,736 KB
スコア	4,377
平均クエリ数	956.53
最終ジャッジ日時	2022-06-12 16:17:30
合計ジャッジ時間	43,522 ms
ジャッジサーバーID （参考情報）	judge13 / judge10
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	275 ms 99,372 KB
testcase_01	AC	424 ms 100,952 KB
testcase_02	AC	340 ms 100,784 KB
testcase_03	AC	399 ms 102,736 KB
testcase_04	AC	390 ms 101,116 KB
testcase_05	AC	393 ms 101,088 KB
testcase_06	AC	406 ms 100,624 KB
testcase_07	AC	366 ms 101,324 KB
testcase_08	AC	388 ms 100,972 KB
testcase_09	AC	405 ms 102,368 KB
testcase_10	AC	376 ms 101,472 KB
testcase_11	AC	266 ms 99,992 KB
testcase_12	AC	337 ms 101,012 KB
testcase_13	AC	407 ms 101,064 KB
testcase_14	AC	402 ms 101,812 KB
testcase_15	AC	427 ms 100,620 KB
testcase_16	AC	381 ms 101,612 KB
testcase_17	AC	387 ms 101,220 KB
testcase_18	AC	356 ms 101,292 KB
testcase_19	AC	394 ms 101,308 KB
testcase_20	AC	351 ms 101,376 KB
testcase_21	AC	312 ms 100,828 KB
testcase_22	AC	341 ms 100,936 KB
testcase_23	AC	388 ms 102,528 KB
testcase_24	AC	408 ms 101,728 KB
testcase_25	AC	366 ms 100,440 KB
testcase_26	AC	317 ms 100,368 KB
testcase_27	AC	371 ms 101,540 KB
testcase_28	AC	371 ms 101,440 KB
testcase_29	AC	389 ms 102,000 KB
testcase_30	AC	335 ms 101,584 KB
testcase_31	AC	374 ms 101,436 KB
testcase_32	AC	380 ms 101,400 KB
testcase_33	AC	398 ms 101,228 KB
testcase_34	AC	423 ms 101,568 KB
testcase_35	AC	378 ms 101,292 KB
testcase_36	AC	395 ms 101,780 KB
testcase_37	AC	358 ms 101,304 KB
testcase_38	AC	375 ms 101,264 KB
testcase_39	AC	380 ms 101,220 KB
testcase_40	AC	241 ms 98,932 KB
testcase_41	AC	410 ms 102,608 KB
testcase_42	AC	379 ms 100,936 KB
testcase_43	AC	399 ms 101,348 KB
testcase_44	AC	400 ms 101,572 KB
testcase_45	AC	397 ms 100,956 KB
testcase_46	AC	387 ms 101,404 KB
testcase_47	AC	372 ms 101,528 KB
testcase_48	AC	372 ms 102,108 KB
testcase_49	AC	367 ms 102,244 KB
testcase_50	AC	389 ms 101,484 KB
testcase_51	AC	393 ms 101,716 KB
testcase_52	AC	306 ms 101,096 KB
testcase_53	AC	392 ms 100,796 KB
testcase_54	AC	398 ms 101,928 KB
testcase_55	AC	374 ms 100,676 KB
testcase_56	AC	378 ms 101,708 KB
testcase_57	AC	390 ms 100,336 KB
testcase_58	AC	380 ms 101,708 KB
testcase_59	AC	354 ms 101,668 KB
testcase_60	AC	398 ms 101,772 KB
testcase_61	AC	369 ms 101,612 KB
testcase_62	AC	387 ms 100,632 KB
testcase_63	AC	376 ms 100,968 KB
testcase_64	AC	378 ms 102,048 KB
testcase_65	AC	390 ms 100,864 KB
testcase_66	AC	372 ms 101,096 KB
testcase_67	AC	375 ms 101,752 KB
testcase_68	AC	374 ms 102,260 KB
testcase_69	AC	376 ms 101,636 KB
testcase_70	AC	222 ms 98,764 KB
testcase_71	AC	379 ms 101,060 KB
testcase_72	AC	353 ms 100,720 KB
testcase_73	AC	392 ms 101,556 KB
testcase_74	AC	399 ms 101,520 KB
testcase_75	AC	385 ms 101,652 KB
testcase_76	AC	368 ms 101,444 KB
testcase_77	AC	385 ms 101,028 KB
testcase_78	AC	398 ms 102,084 KB
testcase_79	AC	372 ms 102,100 KB
testcase_80	AC	303 ms 100,980 KB
testcase_81	AC	381 ms 101,192 KB
testcase_82	AC	402 ms 101,596 KB
testcase_83	AC	394 ms 101,704 KB
testcase_84	AC	380 ms 101,200 KB
testcase_85	AC	393 ms 100,964 KB
testcase_86	AC	378 ms 101,304 KB
testcase_87	AC	374 ms 100,700 KB
testcase_88	AC	375 ms 102,104 KB
testcase_89	AC	389 ms 102,224 KB
testcase_90	AC	420 ms 101,736 KB
testcase_91	AC	405 ms 101,680 KB
testcase_92	AC	394 ms 101,152 KB
testcase_93	AC	417 ms 101,324 KB
testcase_94	AC	382 ms 102,128 KB
testcase_95	AC	357 ms 100,896 KB
testcase_96	AC	393 ms 101,112 KB
testcase_97	AC	397 ms 101,476 KB
testcase_98	AC	404 ms 100,600 KB
testcase_99	AC	369 ms 102,284 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() < 0.4:
          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.6:
      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

結果

テストケース

ソースコード