小さなサメ

質問する

N×Nサイズの空間にはM匹の魚と小さなサメが1匹います.スペース1×1サイズの正方形の格子に分けます.1つの格子には最大1匹の魚が存在する.
小さなサメも魚も大きさがあり、この大きさは自然数です.最初は小さいサメの大きさが2で、小さいサメは1秒程度で隣の1マスを移動します.
小さなサメは自分より大きい魚の格子を通ることができず、残りの格子は通ることができます.サメは自分より小さい魚しか食べられません.そのため、同じ大きさの魚は食べられませんが、魚の格子があって行けます.
サメがどこに移動するかを決める方法は以下の通りです.
空間に食べられる魚がなければ、サメはお母さんのサメに助けを求めます.もし魚が

食べられるなら、私はそれを食べに行きます.

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

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

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

サメの移動に1秒かかると仮定し、魚を食べる時間はありません.つまり、サメが魚が食べられる場所に移動すると、移動しながら魚を食べます.魚を食べたら、その一格は空いていました.
サメは自分の大きさと同じ数の魚を食べるたびに、大きさが1つ増えます.例えば、大きさ2の小さなサメが2匹の魚を食べる場合、大きさは3です.
空間状態にあるときは、小さなサメが数秒以内にお母さんのサメに助けを求めずに魚を食べることができるかどうかを見るプログラムを作成します.

入力

第1行は空間サイズN(2≦N≦20)を与える.
2行目から、N行スペースを与えた状態.空間の状態は0、1、2、3、4、5、6、9からなり、以下の意味を持つ.

0:スペース

1、2、3、4、5、6:格の中の魚の大きさ

9:サメの位置

小さなサメが空間に1匹います.

しゅつりょく

最初の行はサメがお母さんのサメの助けを求めずに魚を食べる時間を出力します.

解決策

魚を食べるときは最短距離を歩かなければならないのでbfsを使います.

グリッド回りに魚の数を数え、サメの位置を把握してsr、scに設定します.

時間は0から始まり、魚の数が0になるまでドアを回します.

whileゲート内でbfsを行い、bfsはsr、scを加え、距離を0に初期化した.

アクセスアレイを作成し、初期最小距離の最大値を1 e 9に設定し、十分な大きさにします.

列の許しを求める前に、4つの方向を探索し、街にいて訪問せず、サメ以下であればif門に入る.

アクセス処理.

では、魚がサメより小さい場合、距離を最小距離に更新し、最小距離リストに追加します.

以降探索する区間が最小距離より小さい場合は,キューに入れて探索する.

qが空の場合、食べる魚を選択し、sortを使用して距離、行座標、列座標の順に並べ替えて返す必要があります.

bfsが完了すると、最短距離の魚に距離を増やし、出発地点を更新します.

内部はサメが食べる魚の数に応じてサメの大きさを更新します.

from collections import deque
N =int(input())

grid = [list(map(int,input().split())) for _ in range(N)]

#방향 
dr = [-1,0,1,0]
dc = [0,-1,0,1]

#물고기수 
fish = 0
#상어 최초 크기 
shark = 2

#먹은 물고기 수 
eat = 0

#아기상어 위치가 시작 위치
for r in range(N):
    for c in range(N) :
        #상어 위치 
        if grid[r][c] == 9 :
            sr,sc = r,c
            grid[r][c] = 0
        #물고기 수 
        elif 0<grid[r][c] <=6 :
            fish += 1 

#아기상어 시작 위치와 크기 배열에 넣기 

def bfs(sr,sc) :

    q = deque([(sr,sc,0)])

    #물고기까지 거리를 담을 리스트 
    dist_lst = [] 
    #방문배열 
    visited =[[0]*N for _ in range(N)]
    visited[sr][sc] = 1 

    min_dist = 1e9

    #큐가 빌때까지 
    while q :
        #꺼내고 
        r,c,dist = q.popleft()
        #4방향 탐색 
        for d in range(4) :
            nr = r + dr[d]
            nc = c + dc[d]
            #거리 안에 있으면서 방문하지 않았을 때 #나보다 작거나 같으면 방문한다. 
            if 0<=nr<N and 0<=nc <N and not visited[nr][nc] and grid[nr][nc] <= shark :
                visited[nr][nc] = 1 
                #상어보다 작으면 해당 상어까지 거리를 최소거리로 갱신하고 후보에 넣는다. 
                if 0< grid[nr][nc] < shark :
                    min_dist = dist 
                    dist_lst.append((nr,nc,dist+1))
                #한 칸 더 탐색할 곳이 최소거리보다 작다면 큐에 추가해서 탐색한다. 
                if dist + 1 <=min_dist :
                    q.append((nr,nc,dist+1 ))
        
    if dist_lst :
        dist_lst.sort(key=lambda x:(x[2],x[0],x[1]))
        return dist_lst[0]
        
#소요시간 
time = 0
#남은 물고기가 있을 때 
while fish :
    #현 위치에서 가장 가까우면서 먹을 수 있는 물고기를 찾는다. 
    result = bfs(sr,sc)

    #먹을 물고기가 없으면 멈춘다. 
    if not result :
        break 
    #물고기를 찾으면 그 위치가 내 자리 
    sr,sc = result[0],result[1]
    #걸린 시간에 물고기한테 가는데 걸린 거리를 더한다. 
    time += result[2]

    #먹은 물고기
    eat += 1 
    #남은 물고기 
    fish -=1 
    #상어 크기와 먹은 물고기가 같으면 
    if shark == eat :
        #상어 크기 더하고 
        shark += 1 
        #물고기 수 추가 
        eat = 0
    
    #물고기 먹었으니까 자리 없애기 
    grid[sr][sc] = 0
print(time)