白駿16236号:小さなサメ-Swift

https://www.acmicpc.net/problem/16236
難易度金貨4🥇
アルゴリズム分類:実装,bfs
🧐 質問へのアクセス
実際の運用が必要な実施問題.
最初からまじめに読んで問題を解いてこそ、時間の無駄を減らすことができる.
また、サメを食べるときは(グラフを0に設定したり、サメの赤ちゃん情報を更新したりするなど)処理してこそ、間違いを避けることができます.
コード#コード#
1.bfsナビゲーションコード
サメの赤ちゃんの情報はshark=(x座標,y座標,サメサイズ)で管理されています.
普通にbfs検索すればいいので、食べられるサメの中で最短距離のものをfishListに入れます.
そして問題で提案されたソート基準に従って食べるサメを選択し、小さなサメの情報と時間を更新します.

func bfs() -> Bool {
    var queue = [(shark.0, shark.1, 0)]
    var idx = 0
    
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    
    var visit = Array(repeating: Array(repeating: false, count: n), count: n)
    visit[shark.0][shark.1] = true
    
    var dist = Int.max
    var fishList = [(Int,Int)]()
    
    while queue.count > idx {
        let (x,y,cnt) = queue[idx]
        idx += 1
        
        if cnt > dist {continue}
        
        if (1..<shark.2).contains(graph[x][y]) {
            dist = cnt
            fishList.append((x,y))
        }
        
        for i in 0..<4 {
            let (nx,ny) = (x+dx[i], y+dy[i])
            if (0..<n).contains(nx) && (0..<n).contains(ny) && !visit[nx][ny] && graph[nx][ny] <= shark.2 {
                visit[nx][ny] = true
                queue.append((nx,ny,cnt+1))
            }
        }
    }
    
    if fishList.isEmpty {
        return false
    }
    
    fishList.sort{
        if $0.0 == $1.0 {
            return $0.1 < $1.1
        }
        return $0.0 < $1.0
    }
    
    let target = fishList.first!
    eatCnt += 1
    
    if eatCnt == shark.2 {
        shark.2 += 1
        eatCnt = 0
    }
    
    graph[target.0][target.1] = 0
    shark = (target.0, target.1, shark.2)
    
    time += dist
    return true
}

完全なコード

//16236번 아기 상어

let n = Int(readLine()!)!
var graph = [[Int]]()

var shark = (-1,-1,-1)
var eatCnt = 0

for i in 0..<n {
    let t = readLine()!.split(separator: " ").map{Int(String($0))!}
    graph.append(t)
    
    if let j = t.firstIndex(of: 9) {
        shark = (i,j,2)
        graph[i][j] = 0
    }
}

var time = 0

func bfs() -> Bool {
    var queue = [(shark.0, shark.1, 0)]
    var idx = 0
    
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    
    var visit = Array(repeating: Array(repeating: false, count: n), count: n)
    visit[shark.0][shark.1] = true
    
    var dist = Int.max
    var fishList = [(Int,Int)]()
    
    while queue.count > idx {
        let (x,y,cnt) = queue[idx]
        idx += 1
        
        if cnt > dist {continue}
        
        if (1..<shark.2).contains(graph[x][y]) {
            dist = cnt
            fishList.append((x,y))
        }
        
        for i in 0..<4 {
            let (nx,ny) = (x+dx[i], y+dy[i])
            if (0..<n).contains(nx) && (0..<n).contains(ny) && !visit[nx][ny] && graph[nx][ny] <= shark.2 {
                visit[nx][ny] = true
                queue.append((nx,ny,cnt+1))
            }
        }
    }
    
    if fishList.isEmpty {
        return false
    }
    
    fishList.sort{
        if $0.0 == $1.0 {
            return $0.1 < $1.1
        }
        return $0.0 < $1.0
    }
    
    let target = fishList.first!
    eatCnt += 1
    
    if eatCnt == shark.2 {
        shark.2 += 1
        eatCnt = 0
    }
    
    graph[target.0][target.1] = 0
    shark = (target.0, target.1, shark.2)
    
    time += dist
    return true
}

while true {
    if !bfs() {
        print(time)
        break
    }
}

1行の評価:これは少し厄介な実施問題です.