E - Akari

[hxrxchang]

https://atcoder.jp/contests/abc182/tasks/abc182_e

問題概要

H * Wのグリッドに電球とブロックが置かれている。 電球は縦方向と横方向にブロックが置かれている場所まで光を放つことができる。 電球が置かれている場所を含めて、ブロックを除いて光が到達したマスはいくつか？

解き方

• "横方向にライトをブロックが見つかるまで照らしていく、またライトが見つかったらブロックが見つかるまで照らしていくのを繰り返す。これを反対方向にも行う" をH行分
• "縦方向にライトをブロックが見つかるまで照らしていく、またライトが見つかったらブロックが見つかるまで照らしていくのを繰り返す。これを反対方向にも行う" をW列分 やって行けばOK 計算量は W * 2 * H + H * 2 * W で 最大9000000。

func solve() {
    in := getInts()
    h, w, n, m := in[0], in[1], in[2], in[3]
    // 0: 何もない, 1: ライト, 2: ブロック
    grid := make([][]int, h)
    for i := 0; i < h; i++ {
        grid[i] = make([]int, w)
    }

    lighted := make([][]bool, h)
    for i := 0; i < h; i++ {
        lighted[i] = make([]bool, w)
    }

    for i := 0; i < n; i++ {
        in := getInts()
        a, b := in[0] - 1, in[1] - 1
        grid[a][b] = 1
    }

    for i := 0; i < m; i++ {
        in := getInts()
        a, b := in[0] - 1, in[1] - 1
        grid[a][b] = 2
    }

    for i := 0; i < h; i++ {
        isLight := false
        for j := 0; j < w; j++ {
            if grid[i][j] == 1 {
                isLight = true
                lighted[i][j] = true
            } else if grid[i][j] == 2 {
                isLight = false
            } else if isLight {
                lighted[i][j] = true
            }
        }
        isLight = false
        for j := w - 1; j >= 0; j-- {
            if grid[i][j] == 1 {
                isLight = true
                lighted[i][j] = true
            } else if grid[i][j] == 2 {
                isLight = false
            } else if isLight {
                lighted[i][j] = true
            }
        }
    }

    for i := 0; i < w; i++ {
        isLight := false
        for j := 0; j < h; j++ {
            if grid[j][i] == 1 {
                isLight = true
                lighted[j][i] = true
            } else if grid[j][i] == 2 {
                isLight = false
            } else if isLight {
                lighted[j][i] = true
            }
        }
        isLight = false
        for j := h - 1; j >= 0; j-- {
            if grid[j][i] == 1 {
                isLight = true
                lighted[j][i] = true
            } else if grid[j][i] == 2 {
                isLight = false
            } else if isLight {
                lighted[j][i] = true
            }
        }
    }

    ans := 0
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if lighted[i][j] {
                ans++
            }
        }
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc182/submissions/54457793