r行c列のすべてのセルを黒にするために必要な最小操作回数を求めるC++プログラム

問題概要

2つの整数 r、c と、n × m のサイズを持つグリッドが与えられます。グリッドには黒く塗られたセルと、白いままのセルが混在しています。1回の操作では、任意の黒いセルを1つ選び、次の2つのうちどちらか一方を必ず実行します。

• そのセルが属する行全体を黒に塗る
• そのセルが属する列全体を黒に塗る

このとき、r行目とc列目のセルを黒にするために必要な最小の操作回数を求めます。どうしても実現できない場合は -1 を返してください。

たとえば、入力が次のようなグリッドだったとします。

r = 0、c = 3 のとき、出力は 1 になります。これは、1行目を丸ごと黒く塗り替えることで、次の状態にできるからです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

n := グリッドの行数
m := グリッドの列数
ans := 非常に大きい値(事実上の無限大)
i := 0 から n-1 までの各行について:
    j := 0 から m-1 までの各列について:
        matrix[i][j] が 'B'(黒)である場合:
            ans := ans と {(i ≠ r なら 1、そうでなければ 0) + (j ≠ c なら 1、そうでなければ 0)} の小さい方
ans が 2 より大きい場合:
    -1 を返す
そうでなければ:
    ans を返す

アルゴリズムのポイント

黒いセル (i, j) を操作の起点としたとき、目標のセル (r, c) を黒くするまでのコストは次のように見積もることができます。

• (i, j) = (r, c) の場合:すでに黒なので、追加の操作は不要(0回)
• i = r または j = c の場合:その行または列を1回塗るだけでよい(1回)
• どちらにも一致しない場合:行→列、または列→行の順に2回の操作で到達できる(2回)

つまり、盤面に黒いセルが1つでも存在すれば答えは必ず2以下になり、ans が 2 を超えるのは「黒いセルが1つも存在しない」場合だけです。この性質のおかげで、-1 を返すべきかどうかは ans > 2 という判定だけで簡単にわかります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<char>> matrix, int r, int c) {
    int n = matrix.size();
    int m = matrix[0].size();
    int ans = 999999;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == 'B') {
                ans = min(ans, (i != r) + (j != c));
            }
        }
    }
    if (ans > 2) {
        return -1;
    }
    else
        return ans;
}

int main() {
    vector<vector<char>> matrix = { { 'W', 'B', 'W', 'W', 'W' },
                                    { 'B', 'B', 'B', 'W', 'B' },
                                    { 'W', 'W', 'B', 'B', 'B' } };
    int r = 0, c = 3;
    cout << solve(matrix, r, c) << endl;
}

計算量

グリッドの全セルを一度走査するだけなので、時間計算量は O(n × m)、追加のメモリ使用量は O(1) と、非常に効率的な解法になっています。

入力

{ { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B' }, { 'W', 'W', 'B', 'B', 'B' } }, 0, 3

出力

1