Submission #18504754

Source Code Expand

Copy
```from copy import copy
from time import time
from collections import deque
from random import randrange

start=time()

H,W,K,sr,sc=map(int,input().split())
sr=sr-1
sc=sc-1
s=[]
for h in range(H):
s.append(input())
N=int(input())
food=[[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(N):
fr,fc,F,D=map(int,input().split())
food[fr-1][fc-1]=[F,D]

step=[[1,0],[-1,0],[0,1],[0,-1]]
dir=["D","U","R","L"]

def BFS(score,r,c,course,cnt,eat):

seen=[[0]*W for _ in range(H)]

q=deque([[score,r,c,course,cnt,eat]])
CD=[]
seen[r][c]=1
mx=K
while q:
sc,h0,w0,c,count,eat1=q.popleft()
if sc>0:
if count>mx:continue
elif count==mx:
CD.append([sc, h0, w0, c, count, eat1])
elif count<mx:
mx=count
CD.append([sc, h0, w0, c, count, eat1])
else:
if count>=mx:continue

for i in range(4):
h1=h0+step[i][0]
w1=w0+step[i][1]
if 0<=h1<H and 0<=w1<W and seen[h1][w1]==0 and s[h1][w1]==".":
tmp_score = copy(sc)
tmp_course = copy(c)
tmp_eat=copy(eat1)
if (food[h1][w1][0]-food[h1][w1][1]*count)>0:
tmp_eat.append([h1,w1])
tmp_score+=food[h1][w1][0]-food[h1][w1][1]*count
elif (food[h1][w1][0]-food[h1][w1][1]*count)<0:
continue
tmp_course+=dir[i]
q.append([tmp_score,h1,w1,tmp_course,count+1,tmp_eat])
seen[h1][w1]=1
if len(CD)>0:
idx=randrange(len(CD))
sc,h0,w0,c,count,eat1=CD[idx]

return sc,h0,w0,c,count,eat1

anss=[]
while time()-start<9.5:
#for n in range(3):
ans=[]
score=0
h0=sr
w0=sc
hp=h0
wp=w0
course=""
cnt=0

while True:
score1,h1,w1,course,cnt,eat=BFS(0,h0,w0,"",cnt,[])
if len(course)==0:
for i in range(K-len(ans)):
ans+="-"
if cnt==K:
ans.append(course)
score+=score1
break
score+=score1
ans.append(course)
for fr,fc in eat:
food[fr][fc]=[0,0]
h0=h1
w0=w1

anss.append([score,ans])

Ans=anss[anss.index(max(anss))][1]
print("".join(Ans))

```

#### Submission Info

Submission Time 2020-11-30 22:41:09+0900 B - Food Collector SleepyPuppy PyPy3 (7.3.0) 18182 2509 Byte AC 9688 ms 159072 KB

#### Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1741 / 20000 2441 / 20000 1873 / 20000 1127 / 20000 1900 / 20000 2380 / 20000 2018 / 20000 1627 / 20000 1121 / 20000 1954 / 20000
Status
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
Set Name Test Cases