paiza Qiita コラボ S問題 思い出の屋上

Swiftでやりました。

問題概要

マス状のエリアがある。陣取っているものがすでにいる。空いているできるだけ広い領域を調べる。領域のサイズはマンハッタン距離で決定される。サイズが4のときは中心からマンハッタン距離が4以内のマスが陣地になる。

やり方

答になる空き領域をE、そのサイズをSとする。Eはどこかの領域(R)と接する。そのRをS+1だけ広げるとEの中心を覆う。
よって、すでに陣取っているものの領域を1つずつ広くしていくと、空きが徐々になくなっていって、最後にEの中心がRによって覆われる。
空きマスの数を管理しておいて、0になるまで行う。
正解と判断されたがちょっと自信がないw

func readInt() -> Int {
    Int(readLine()!)!
}

func readInts() -> [Int] {
    readLine()!.split(separator: " ").map { Int(String($0))! }
}

let hwm = readInts()
let h = hwm[0]
let w = hwm[1]
let m = hwm[2]

var field = [[Bool]](repeating: [Bool](repeating: false, count: w), count: h)
var counter = h * w

func draw(r: Int, c: Int, s: Int) {
    if s == 0 {
        if field[r][c] == false {
            field[r][c] = true
            counter -= 1
        }
    } else {
        for (bR, bC, mR, mC) in [(-1, 0, 1, 1), (0, 1, 1, -1), (1, 0, -1, -1), (0, -1, -1, 1)] {
            //b:base m:move
            for m in 0..<s {
                let drawR = r + bR * s + mR * m
                let drawC = c + bC * s + mC * m
                if drawR >= 0 && drawR <= h - 1 && drawC >= 0 && drawC <= w - 1 {
                    if field[drawR][drawC] == false {
                        field[drawR][drawC] = true
                        counter -= 1
                    }
                }
            }
        }
    }
}

var center: [(Int, Int, Int)] = []
for _ in 1...m {
    let rcs = readInts()
    let r = rcs[0] - 1
    let c = rcs[1] - 1
    let s = rcs[2]
    center.append((r, c, s))
    for i in 0...s {
        draw(r: r, c: c, s: i)
    }
}

if counter == 0 {
    print(-1)
} else {
    var current = 0
    var expand = 0
    while true {
        expand += 1
        for c in center {
            draw(r: c.0, c: c.1, s: c.2 + expand)
        }
        if counter == 0 {
            print(current)
            break
        }
        current += 1
    }
}

計算量が問題になる場合、必要ないところを削る処理を加えていくとよいでしょう。たとえば、ある領域を広げても空き領域を潰すことがない場合は、その領域はもう必要ないと判断できます。