結果
問題 | No.331 CodeRunnerでやれ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#coding: UTF-8import sysimport reimport itertoolsfrom collections import deque""" defs """def searching_forward(x,y,drct,unsearch,searched_point,maze):s = input()if (s=='Merry Christmas!'):return Trueelif (int(s)==20151224):while (s!='Merry Christmas!'):print('F')s = input()return Trueelse:floor_count = int(s)if (drct==0):for c in range(1,floor_count+1):maze[y][x+c] = 1if (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] = 1if (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] = 1if (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] = 1if (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 Trueprint('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 Trueprint('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 Trueprint('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 Trueprint('L')drct = (drct+1) % 4# for row in maze:# print(row)return Falsedef select_unserch_point(unsearch, searched_point):(x,y) = unsearch.popleft()searched_point[y][x] = 1return x,ydef 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):continueroute[y][x] = prevdrctif(x==dx and y==dy):breakif(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=dxny=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 -= 1elif(nd==1):ny += 1elif(nd==2):nx += 1else:ny -= 1# print(action)nx = sxny = synd = drctwhile True:if(nx==dx and ny==dy):breakac = action.popleft()while (ac!=nd):print('L')nd = (nd+1)%4print('F')if (nd==0):nx += 1elif(nd==1):ny -=1elif(nd==2):nx -= 1elif(nd==3):ny += 1return nx,ny,nd""" main """maze = list( [0]*50 for _ in range(50) )#search pointsearched_point = list( [0]*50 for _ in range(50) )#unsearch pointunsearch = deque()x=25y=25searched_point[y][x]=1#direction 0..right, 1...up, 2...left, 3...downdrct = 0while True:goal = search(x,y,drct,unsearch,searched_point,maze)if (goal):breakdx,dy = select_unserch_point(unsearch,searched_point)x,y,drct = move_unsearch_point(x,y,drct,dx,dy,maze)