Submission #549424

#	Time	Username	Problem	Language	Result	Execution time	Memory
549424		beaconmc	Mecho (IOI09_mecho)	Pypy 3	7 / 100	1093 ms	65536 KiB

mecho

from collections import *
n,s = map(int, input().split())
grid = [list(input()) for i in range(n)]

hives = []
start = []
end = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == "M":
            start = [i,j]
        elif grid[i][j] == "D":
            end = [i,j]
        elif grid[i][j] == "H":
            hives.append([i,j])
            grid[i][j] = 0
def bfsinit():           
    d = deque()
    for i in hives:
        d.append(i+[0])
    while len(d):
        node = d.popleft()

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n:
                if grid[a][b] == "G" or grid[a][b] == "M":
                    d.append([a,b,node[2]+1])
                    grid[a][b] = node[2]+1

def test(time):
    d = deque()
    visited = [[False for i in range(n)] for i in range(n)]
    d.append(start+[0])
    while len(d):
        node = d.popleft()
        if node[0] == end[0] and node[1]==end[1]:
            return True

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n and not visited[a][b]:
                if grid[a][b]=="T":
                    continue
                if grid[a][b] == "D" or int(grid[a][b]) >= time+(node[2])//s+1:
                    d.append([a,b,node[2]+1])
                    visited[a][b] = True
    return False
    
bfsinit()


for i in range(100, -1 ,-1):
    if test(i):
        print(i)
        break

• Subtask 1: 7 / 100