白駿#16236サメ(Python)

質問リンク

の魚が1匹以上食べられるなら、一番近い魚を食べに行きます.

街は、サメがいる格子から魚がいる格子に移動する際に通過する格子の個数の最高値です.

街から近い魚が多いなら、一番上の魚、何匹も魚がいるなら、一番左の魚を食べます.

これは問題の核心であり,我々が推測したように,bfsを用いて最短距離の関連問題を探すことである.
毎回1匹の魚を食べる時、全部のspaceに対してbfsを行って、食べられる魚をすべて整理して、無限に繰り返してその中で最も条件に合った1匹の魚を食べます.
魚が1匹も食べられないまで(if not food)繰り返します.
時間がかかるように見えますが、196 msしか使いませんでした.
実はゆっくり見ると、dfsとbfsは少なくともかつてしたことをしません.
従ってarr全体の大きさ(ここではN*N)の時間的複雑さのみを有する.
似たようなarrを何度も探索しても、あまり時間がかからないので、あまり心配しないでください.
これは可読性を保つために非常に努力しているコードです.

import sys

N = int(sys.stdin.readline().rstrip())

space = []
for _ in range(N):
    space.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 처음 아기 상어의 크기는 2
# 1 두개를 먹으면 3이 된다. 

# bfs로 자기가 먹을 수 있는 물고기를 찾는다. 
# 물고기 위치와 거리를 저장해두고, 거리 -> y좌표 -> x좌표 순으로 정렬해준다. 
# 먹을 수 있는 거 다 먹고 이동시간에 더한다. 
# 반복.

class BabyShark:
    def __init__(self, y, x, size):
        self.y = y
        self.x = x
        self.size = size
        self.cnt = 0
        self.time = 0
    
    def move(self, distance, y, x):
        self.time += distance
        self.y = y
        self.x = x

    def eat(self):
        self.cnt += 1
        if self.cnt == self.size:
            self.size += 1
            self.cnt = 0


DIRECTIONS = [(-1,0), (1,0), (0,-1), (0,1)]

if __name__ == '__main__':

    for i in range(N):
        for j in range(N):
            if space[i][j] == 9:
                space[i][j] = 0
                babyShark = BabyShark(i, j, 2)
                break

    while True:
        visited = [[False] * N for _ in range(N)]
        food = []

        q = [(babyShark.y, babyShark.x)]
        distance = 0
        while q:
            q_cpy = q[:]
            q = []
            distance += 1
            for y, x in q_cpy:
                for dy, dx in DIRECTIONS:
                    if not (0 <= y+dy < N and 0 <= x+dx < N):
                        continue
                    if visited[y+dy][x+dx]:
                        continue
                    if space[y+dy][x+dx] > babyShark.size:
                        continue
                    q.append((y+dy, x+dx))
                    visited[y+dy][x+dx] = True
                    if 0 < space[y+dy][x+dx] < babyShark.size:
                        food.append((distance, y+dy, x+dx))

        if not food:
            print(babyShark.time)
            exit()

        food.sort()
        best_food = food[0]
        best_food_distance, best_food_y, best_food_x = best_food
        babyShark.move(best_food_distance, best_food_y, best_food_x)
        babyShark.eat()
        space[best_food_y][best_food_x] = 0