白駿2933号:鉱物-Swift

https://www.acmicpc.net/problem/xxxx
難易度-金貨2🥇
アルゴリズム分類:実装
🧐 質問へのアクセス
見ると金色の2問なので、思ったより緊張しています
実装の問題は、最終的に実装する必要がある関数は次のとおりです.
鉱物

を左側または右側から消去

鉱物を消去する場合は、関連する鉱物が孤立していることを確認してください.

孤立すると重力により

移動する.
コード#コード#
1.左または右から鉱物を消去

let heightList = readLine()!.split(separator: " ").map{Int(String($0))!}
var leftTurn = true

for height in heightList {
    //높이 height의 막대기를 던져서 미네랄 하나 제거
    if leftTurn {
        if let idx = graph[r-height].firstIndex(of: true) {
            graph[r-height][idx] = false
            //삭제한 미네랄 기준 상하좌우 네방향 탐색 시작
            let x = r-height, y = idx
            let start = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for (cx,cy) in start {
                isIsolated(cx, cy)
            }
        }
        
    } else {
        if let idx = graph[r-height].lastIndex(of: true) {
            graph[r-height][idx] = false
        
            let x = r-height, y = idx
            let start = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for (cx,cy) in start {
                isIsolated(cx,cy)
            }
        }
    }
    leftTurn.toggle()
}

leftTurnという変数を使って投げ方向を調整します
対応する方向に投影し、isIsolate関数を上、下、左、右に呼び出します.
私はgraphを記号があるものに変えてtrueで表し、記号がないものはfalseで表すので、コードはそうです.
2.孤立した鉱物の破片がないか確認する

//dfs탐색하고 고립된 조각 반환하기
func dfs(_ x: Int, _ y: Int) -> [(Int,Int)]? {
    //dfs탐색
    var visit = Array(repeating: Array(repeating: false, count: c), count: r)
    var stack = [(x,y)]
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    
    while !stack.isEmpty {
        let (cx,cy) = stack.removeLast()
        //땅에 닿은경우, 중력영향을 받지 않는다.
        if cx == r-1 {
            return nil
        }
        if !visit[cx][cy] {
            visit[cx][cy] = true
            for i in 0..<4 {
                let (nx,ny) = (cx+dx[i],cy+dy[i])
                if (0..<r).contains(nx) && (0..<c).contains(ny) && !visit[nx][ny] && graph[nx][ny] {
                    stack.append((nx,ny))
                }
            }
        }
    }
    //고립된 미네랄의 index를 target에 담아서 return
    var target = [(Int,Int)]()
    for (idx, arr) in visit.enumerated() {
        for (jdx,value) in arr.enumerated() where value {
            graph[idx][jdx] = false
            target.append((idx,jdx))
        }
    }
    return target
}

dfsで実現し,中間のcx=r−1,すなわち,地面に接触すれば孤立ではないと考えられる.
そしてtargetに孤立したミネラルのindexを入れました
難しくないでしょう.
3.孤立している場合は重力で移動

//고립되어 있는지 확인하기
func isIsolated(_ x: Int, _ y: Int) {
    //탐색안해도 되면 return
    guard (0..<r).contains(x) && (0..<c).contains(y) && graph[x][y] else {
        return
    }
    //고립된 미네랄이 없다면 return
    guard let target = dfs(x, y) else {
        return
    }
    
    //move만큼 이동할 수 있는지 체크
    for move in 1...100 {
        //미네랄을 move만큼 이동
        let newTarget = target.map{($0.0+move, $0.1)}
        //그래프 범위안인지, 다른 미네랄과 안겹치는지 검사
        var canMove = true
        newTarget.forEach{
            if !((0..<r).contains($0.0) && (0..<c).contains($0.1) && !graph[$0.0][$0.1]) {
                canMove = false
            }
        }
        //더이상 이동할 수 없다면, 이전 move만큼 이동시킨후 종료
        if !canMove {
            let cnt = move - 1
            target.forEach{
                graph[$0.0+cnt][$0.1] = true
            }
            break
        }
    }
}

最初の2つのguard文を通過すると、ターゲットは孤立した鉱物グループを格納します.
targetのすべての要素がmoveで移動し、元のグラフィックと重複しない&&範囲外であることを確認するだけです.
移動できない場合は、現在のmove-1の値を移動し、グラフィックを更新して終了します.
完全なコード

//2933번 미네랄
let t = readLine()!.split(separator: " ").map{Int(String($0))!}
var (r,c) = (t[0],t[1])
var graph = [[Bool]]()

//dfs탐색하고 고립된 조각 반환하기
func dfs(_ x: Int, _ y: Int) -> [(Int,Int)]? {
    //dfs탐색
    var visit = Array(repeating: Array(repeating: false, count: c), count: r)
    var stack = [(x,y)]
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    
    while !stack.isEmpty {
        let (cx,cy) = stack.removeLast()
        //땅에 닿은경우, 중력영향을 받지 않는다.
        if cx == r-1 {
            return nil
        }
        if !visit[cx][cy] {
            visit[cx][cy] = true
            for i in 0..<4 {
                let (nx,ny) = (cx+dx[i],cy+dy[i])
                if (0..<r).contains(nx) && (0..<c).contains(ny) && !visit[nx][ny] && graph[nx][ny] {
                    stack.append((nx,ny))
                }
            }
        }
    }
    //고립된 미네랄의 index를 target에 담아서 return
    var target = [(Int,Int)]()
    for (idx, arr) in visit.enumerated() {
        for (jdx,value) in arr.enumerated() where value {
            graph[idx][jdx] = false
            target.append((idx,jdx))
        }
    }
    return target
}

//고립되어 있는지 확인하기
func isIsolated(_ x: Int, _ y: Int) {
    //탐색안해도 되면 return
    guard (0..<r).contains(x) && (0..<c).contains(y) && graph[x][y] else {
        return
    }
    //고립된 미네랄이 없다면 return
    guard let target = dfs(x, y) else {
        return
    }
    
    //move만큼 이동할 수 있는지 체크
    for move in 1...100 {
        //미네랄을 move만큼 이동
        let newTarget = target.map{($0.0+move, $0.1)}
        //그래프 범위안인지, 다른 미네랄과 안겹치는지 검사
        var canMove = true
        newTarget.forEach{
            if !((0..<r).contains($0.0) && (0..<c).contains($0.1) && !graph[$0.0][$0.1]) {
                canMove = false
            }
        }
        //더이상 이동할 수 없다면, 이전 move만큼 이동시킨후 종료
        if !canMove {
            let cnt = move - 1
            target.forEach{
                graph[$0.0+cnt][$0.1] = true
            }
            break
        }
    }
}
//미네랄 재조정
func downMineral() {}

for _ in 0..<r {
    let input = Array(readLine()!).map{ $0 == "." ? false : true}
    graph.append(input)
}

let n = Int(readLine()!)!
let heightList = readLine()!.split(separator: " ").map{Int(String($0))!}
var leftTurn = true

for height in heightList {
    //높이 height의 막대기를 던져서 미네랄 하나 제거
    if leftTurn {
        if let idx = graph[r-height].firstIndex(of: true) {
            graph[r-height][idx] = false
            //삭제한 미네랄 기준 상하좌우 네방향 탐색 시작
            let x = r-height, y = idx
            let start = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for (cx,cy) in start {
                isIsolated(cx, cy)
            }
        }
        
    } else {
        if let idx = graph[r-height].lastIndex(of: true) {
            graph[r-height][idx] = false
        
            let x = r-height, y = idx
            let start = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for (cx,cy) in start {
                isIsolated(cx,cy)
            }
        }
    }
    leftTurn.toggle()
}

for g in graph {
    print(g.map{$0 ? "x" : "."}.joined(separator: ""))
}

一行の評価:一般的な実施問題ですが、Gold 2よりずっと簡単そうです.