結果

問題 No.331 CodeRunnerでやれ
コンテスト
ユーザー soupesuteaka
提出日時 2016-02-25 20:07:51
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,261 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 81,876 KB
実行使用メモリ 176,784 KB
平均クエリ数 0.06
最終ジャッジ日時 2024-07-16 22:57:26
合計ジャッジ時間 7,747 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other AC * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#coding: UTF-8

import sys
import re
import itertools
from collections import deque

""" defs """

def searching_forward(x,y,drct,unsearch,searched_point,maze):
	s = input()
	if (s=='Merry Christmas!'):
		return True
	elif (int(s)==20151224):
		while (s!='Merry Christmas!'):
			print('F')
			s = input()
		return True
	else:
		floor_count = int(s)
		if (drct==0):
			for c in range(1,floor_count+1):
				maze[y][x+c] = 1
				if (searched_point[y][x+c]==0):
					unsearch.append((x+c,y))
		elif (drct==1):
			for c in range(1,floor_count+1):
				maze[y-c][x] = 1
				if (searched_point[y-c][x]==0):
					unsearch.append((y-c,x))
		elif (drct==2):
			for c in range(1,floor_count+1):
				maze[y][x-c] = 1
				if (searched_point[y][x-c]==0):
					unsearch.append((y,x-c))
		elif (drct==3):
			for c in range(1,floor_count+1):
				maze[y+c][x] = 1
				if (searched_point[y+c][x]==0):
					unsearch.append((y+c,x))

def search(x, y, drct,unsearch,searched_point,maze):
	end = searching_forward(x,y,drct,unsearch,searched_point,maze)
	if (end==True):
		return True
	print('L')
	drct = (drct+1) % 4
#	for row in maze:
#		print(row)

	end = searching_forward(x,y,drct,unsearch,searched_point,maze)
	if (end==True):
		return True
	print('L')
	drct = (drct+1) % 4
#	for row in maze:
#		print(row)
		
	end = searching_forward(x,y,drct,unsearch,searched_point,maze)
	if (end==True):
		return True
	print('L')
	drct = (drct+1) % 4
#	for row in maze:
#		print(row)
		
	end = searching_forward(x,y,drct,unsearch,searched_point,maze)
	if (end==True):
		return True
	print('L')
	drct = (drct+1) % 4
#	for row in maze:
#		print(row)
		
	return False

def select_unserch_point(unsearch, searched_point):
	(x,y) = unsearch.popleft()
	searched_point[y][x] = 1
	return x,y

def move_unsearch_point(sx,sy,drct,dx,dy,maze):
	que = deque()
	route = list( [-2]*50 for _ in range(50) )
	que.append((sx,sy,-1))

	while True:
		(x,y,prevdrct) = que.popleft()
		if (route[y][x] != -2):
			continue

		route[y][x] = prevdrct
		if(x==dx and y==dy):
			break

		if(maze[y][x+1]==1):
			que.append((x+1,y,0))
		if(maze[y-1][x]==1):
			que.append((x,y-1,1))
		if(maze[y][x-1]==1):
			que.append((x-1,y,2))
		if(maze[y+1][x]==1):
			que.append((x,y+1,3))

#	for row in route:
#		print(row)

	action = deque()
	nx=dx
	ny=dy
#	print('sx->',sx,'sy->',sy)
	while True:
		if (nx==sx and ny==sy):
			break
#		print(nx,ny)
		nd=route[ny][nx]
		action.appendleft(nd)
		if(nd==0):
			nx -= 1
		elif(nd==1):
			ny += 1
		elif(nd==2):
			nx += 1
		else:
			ny -= 1

#	print(action)

	nx = sx
	ny = sy
	nd = drct
	while True:
		if(nx==dx and ny==dy):
			break
		ac = action.popleft()
		while (ac!=nd):
			print('L')
			nd = (nd+1)%4
		print('F')
		if (nd==0):
			nx += 1
		elif(nd==1):
			ny -=1
		elif(nd==2):
			nx -= 1
		elif(nd==3):
			ny += 1

	return nx,ny,nd

""" main """
maze = list( [0]*50 for _ in range(50) )
#search point
searched_point = list( [0]*50 for _ in range(50) )
#unsearch point
unsearch = deque()


x=25
y=25
searched_point[y][x]=1
#direction 0..right, 1...up, 2...left, 3...down
drct = 0

while True:
	goal = search(x,y,drct,unsearch,searched_point,maze)
	if (goal):
		break
	dx,dy = select_unserch_point(unsearch,searched_point)
	x,y,drct = move_unsearch_point(x,y,drct,dx,dy,maze)
0