C++で解く！ランプによって照らされたセルの合計数を求めるプログラム

問題の概要

H行・W列のグリッドを考えます。各マスは「空きマス（整頓済み）」か「障害物マス（未整頓）」のいずれかです。このうち、0個以上の空きマスに自由にランプを設置できます。

ランプは上下左右の4方向へ光を放ち、グリッドの端、あるいは最初に障害物マスへ到達する直前までのセルを照らします（障害物のセル自体は照らされません）。もちろん、ランプを置いたセルそのものも照らされます。G[i, j] が「.」ならそのセルは空きマス、「#」なら障害物マスを表します。

空きマスの総数を K とすると、ランプの置き方は全部で 2^K 通り存在します。それぞれの置き方ごとに「1つ以上のランプによって照らされるセルの個数」を求め、それらの総和を 10⁹ + 7 で割った余りとして出力します。

たとえば、入力が次のようなグリッドの場合を考えます。

このとき、出力は 52 になります。

解法の考え方

2^K 通りの配置をすべて列挙すると指数時間かかってしまうため、「各セルが照らされる回数」を数える発想で高速化します。注目しているセルを照らせる位置（同じ行・列で障害物に遮られない範囲）に置けるランプの候補数を src とすると、

• その範囲内から1つ以上のランプを選ぶ方法：（2^src − 1）通り
• 範囲外にあるランプの選び方：2^(K − src) 通り

よって、このセルが照らされる配置は （2^src − 1）× 2^(K − src) 通りであり、これをすべての空きマスについて足し合わせれば答えが求まります。

src を素早く求めるため、各セルから上下左右にどこまで光が届くかを前計算しておきます。上方向 u[i][j]、左方向 l[i][j]、下方向 d[i][j]、右方向 r[i][j] の4つの2次元配列を用意し、行・列方向に順番に走査しながら累積的に更新します。障害物に当たる場合は「そこから先には進めない」ことを表す番兵値を設定するのがポイントです。

アルゴリズムの手順

この問題は、以下の手順に従って解きます。

m := 10^9 + 7
N = 2003
N×N の2次元配列 u, l, r, d と、N^2 個の要素を持つリスト p を定義する
h := グリッドの行数
w := グリッドの列数
tidy := 0（空きマスのカウンタ）
p[0] := 1
for i := 1 to h * w do:
    p[i] := p[i - 1] * 2 mod m   // 2のべき乗を前計算

// 上方向・左方向の到達限界を求める
for i := 0 to h - 1 do:
    for j := 0 to w - 1 do:
        u[i, j] := i
        l[i, j] := j
        if i > 0 then:
            u[i, j] := u[i - 1, j]
        if j > 0 then:
            l[i, j] := l[i, j - 1]
        if matrix[i, j] が '#' なら:
            u[i, j] := i + 1
            l[i, j] := j + 1
        そうでなければ:
            tidy := tidy + 1

// 下方向・右方向の到達限界を求める
for i := h - 1 down to 0 do:
    for j := w - 1 down to 0 do:
        d[i, j] := i
        r[i, j] := j
        if i < h - 1 then:
            d[i, j] := d[i + 1, j]
        if j < w - 1 then:
            r[i, j] := r[i, j + 1]
        if matrix[i, j] が '#' なら:
            d[i, j] := i - 1
            r[i, j] := j - 1

cnt := 0
for i := 0 to h - 1 do:
    for j := 0 to w - 1 do:
        if matrix[i, j] が '#' なら:
            次の反復へスキップ
        // 縦方向のセル数 ＋ 横方向のセル数 − 重複している自分のセル1つ分
        src := d[i, j] + r[i, j] - u[i, j] - l[i, j] + 1
        cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m
return cnt

C++実装例

より理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7, N = 2003;
int u[N][N], l[N][N], r[N][N], d[N][N], p[N * N];

int solve(vector<vector<char>> matrix){
    int h = matrix.size();
    int w = matrix[0].size();
    int tidy = 0;
    p[0] = 1;
    // 2のべき乗を前計算
    for (int i = 1; i <= h * w; ++i)
        p[i] = p[i - 1] * 2 % m;
    // 上方向・左方向の到達限界
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            u[i][j] = i;
            l[i][j] = j;
            if (i)
                u[i][j] = u[i - 1][j];
            if (j)
                l[i][j] = l[i][j - 1];
            if (matrix[i][j] == '#'){
                u[i][j] = i + 1;
                l[i][j] = j + 1;
            }
            else
                ++tidy;
        }
    }
    // 下方向・右方向の到達限界
    for (int i = h - 1; i >= 0; --i){
        for (int j = w - 1; j >= 0; --j){
            d[i][j] = i;
            r[i][j] = j;
            if (i < h - 1)
                d[i][j] = d[i + 1][j];
            if (j < w - 1)
                r[i][j] = r[i][j + 1];
            if (matrix[i][j] == '#'){
                d[i][j] = i - 1;
                r[i][j] = j - 1;
            }
        }
    }
    // 各空きマスが照らされる配置数を合算
    int cnt = 0;
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            if (matrix[i][j] == '#')
                continue;
            int src = d[i][j] + r[i][j] - u[i][j] - l[i][j] + 1;
            cnt = (cnt + (p[src] - 1) * p[tidy - src]) % m;
        }
    }
    return cnt;
}
int main(){
    vector<vector<char>> matrix = { { '.', '.', '#' }, { '#', '.', '.' } };
    cout << solve(matrix) << endl;
}

入力例

{ { '.', '.', '#' }, { '#', '.', '.' } }

出力

52