[Algorithm] BOJ 16236

42963 ワード
algorithm テキストリンク
BOJ 16236サメ
Intro
最初は、これらの魚の位置を保存し、各魚の位置から現在のサメの位置までの距離を求め、優先度が1の魚を使用する方法で実現した.結果はタイムアウトが続いた.
最も近く、最も優先度の高い魚を見つけるためには、BFSを상어가 먹을 수 있는 물고기 개수に調整する必要があります.
しかし、最も近く、最優先の魚が한 번のBFSを見つければ十分です.解決策を共有しましょう
Solution

  • 入力を受信するときに数字9を入力する場合は、サメの位置を保存し、数字9を0に変更します.

  • BFSを使用してサメの現在の位置から最も近い距離の魚を検索し、魚の位置とサメと魚との距離を返します.
  • BFS
    最も近い距離の魚を優先順位で昇順に並べ替え、最初の値を返します.
    魚が食べられなければ不可能な値(位置は(-1,-1)など)を返す.
  • 優先度
    サメ
  • から
    • 距離
  • 位
    • 左側から
  • キロ

  • 入力値で返される魚の位置の値を0に変更します.
    距離によって時間を増やし、食べる魚の数を1増やします.

  • 食べる魚の数がサメの大きさと同じであれば、サメの大きさを1増やし、食べる魚の数を0にリセットします.

  • 魚が食べられないまで2번を繰り返します(2-4번の戻り値は不可能な値です).
    • Code
    Swift
    import Foundation

let n = Int(readLine()!)!
var space = Array<[Int]>()
var sharkPos = (x: -1, y: -1)
var sharkSize = 2
for x in 0..<n {
    space.append(readLine()!.split(separator: " ").map(){Int(String($0))!})
    for (y, num) in space.last!.enumerated() where num == 9 {
        space[x][y] = 0
        sharkPos = (x: x, y: y)
    }
}

func bfs(x: Int, y: Int, n: Int, sharkSize: Int, space: [[Int]]) -> (pos: (x: Int, y: Int), time: Int) {
    var queue = [[x, y, 0]]
    var visited = Array<[Bool]>(repeating: Array(repeating: true, count: n), count: n)
    var fish = [[-1, -1, n*n+1]]
    while !queue.isEmpty {
        let a = queue.removeFirst()
        if fish.count > 1 && fish.last![2] < a[2] { break } 
        else if 1..<sharkSize ~= space[a[0]][a[1]] { fish.append(a); continue }
        else if !visited[a[0]][a[1]] || space[a[0]][a[1]] > sharkSize { continue }
        else { visited[a[0]][a[1]] = false }
        if a[0] != 0 { queue.append([a[0]-1, a[1], a[2]+1]) }
        if a[1] != 0 { queue.append([a[0], a[1]-1, a[2]+1]) }
        if a[1] != n-1 { queue.append([a[0], a[1]+1, a[2]+1]) }
        if a[0] != n-1 { queue.append([a[0]+1, a[1], a[2]+1]) }
    }
    fish.sort(){ (l, r) -> Bool in
        if l[2] < r[2] { return true }
        else if l[2] == r[2] {
            if l[0] < r[0] { return true }
            else if l[0] == r[0] {
                return l[1] < r[1]
            }
            else { return false }
        }
        else { return false }
    }
    return ((fish[0][0], fish[0][1]), fish[0][2])
}

var time = 0
var fishCount = 0
while true {
    let result = bfs(x: sharkPos.x, y: sharkPos.y, n: n, sharkSize: sharkSize, space: space)
    if result.pos.x < 0 { break }
    time += result.time
    sharkPos = result.pos
    fishCount += 1
    if fishCount == sharkSize {
        sharkSize += 1
        fishCount = 0
    }
    space[sharkPos.x][sharkPos.y] = 0
}
print(time)
    Python
    import sys
input = sys.stdin.readline

babyshark = 2
n = int(input().strip())
space = []
babySharkPos = (0, 0)
for x in range(n) :
    space.append(list(map(int, input().strip().split())))
    for y, f in enumerate(space[-1]) : 
        if f == 9 : 
            babySharkPos = (x, y)
            space[-1][y] = 0

def distance(start):
    q = [(start, 0)]
    visited = [[True]*n for _ in range(n)]
    fish = [[(-1, -1), n*n+1]]
    while len(q) :
        a = q.pop(0)
        if len(fish) > 1 and fish[-1][1] < a[1] : break 
        if 0 < space[a[0][0]][a[0][1]] < babyshark : fish.append(a)
        if not visited[a[0][0]][a[0][1]] or space[a[0][0]][a[0][1]] > babyshark : continue
        else : visited[a[0][0]][a[0][1]] = False
        if a[0][0] != 0 : q.append([(a[0][0]-1, a[0][1]), a[1]+1])
        if a[0][1] != 0 : q.append([(a[0][0], a[0][1]-1), a[1]+1])
        if a[0][0] != n-1 : q.append([(a[0][0]+1, a[0][1]), a[1]+1])
        if a[0][1] != n-1 : q.append([(a[0][0], a[0][1]+1), a[1]+1])
    fish.sort(key=lambda x: (x[1], x[0][0], x[0][1]))
    return fish[0]
    
time = 0
fishCount = 0
while True :
    result = distance(babySharkPos)
    if result[0][0] < 0 : break
    time += result[1]
    babySharkPos = result[0]
    fishCount += 1
    if fishCount == babyshark :
        babyshark += 1
        fishCount = 0
    space[babySharkPos[0]][babySharkPos[1]] = 0
print(time)
    委任による合成の合成
    アヒルタイピングに光を流す