問題概要

3行3列のマトリックス状に配置された9つの照明スイッチがある。各スイッチを操作すると、該当する位置および上下左右に隣接するセルの電球状態が反転する（ON⇔OFF）。初期状態の入力が与えられた際、すべてのセルをON状態に切り替えるための最小操作回数を求めよ。

入力・出力仕様

標準入力からは3行にわたり、各行3個の整数が半角スペース区切りで渡される。各値は「0（OFF）」または「1（ON）」を表す。
標準出力には単一の整数のみを出力し、全点灯達成に必要な最少ステップ数を記述する。

動作例

以下の初期配置を例とする。

0 1 1
1 0 0
1 0 1

中央の【2,2】を操作すると周囲の状態が波及し、さらに左上の【1,1】を操作することで全灯達成できる。このケースの最適解は2歩である。

アルゴリズムの設計思想

本問題は離散状態空間における最短経路探索タスクである。重要な観察点として、「同一セルを2回以上操作しても効果は相殺され元の状態に戻る」点が挙げられる。この性質を活用すれば、各位置の選択は「操作する」か「スキップする」かの二値決定で完結するため、探索候補数は最大でも2⁹＝512通りとなる。

実装方針としては再帰関数による深さ優先探索（DFS）を採用する。各段階で現在の盤面状態を変異させながら次のセルへ進み、すべての位置の評価が終了したら盤面検証を行う。ゴール状態（全1）に到達した場合はグローバル最小値と比較更新し、バックトラックによって未訪問パスを試行する。時間計算量はO(2^N×M)であり、3×3グリッドにおいては定数時間で収束する。

C++による実装例

可読性と境界管理の安定性を高めるため、盤面データを5×5の二次元配列で確保し、インデックスは1起点とする。これにより隣接要素への直接アクセス時に範囲外エラーを回避できる。

#include <iostream>
#include <algorithm>

using namespace std;

int board[5][5];      // グリッド状態管理（1-indexed）
int min_ops = 10;     // 最小操作回数（初期値は探索上限より大きめに設定）

// 指定位置(r, c)とその周囲5マス（自身含む）の状態を反転
void invert_switch(int r, int c) {
    board[r][c] ^= 1;
    board[r-1][c] ^= 1;
    board[r+1][c] ^= 1;
    board[r][c-1] ^= 1;
    board[r][c+1] ^= 1;
}

// 盤面の全状態がON（1）であることを検証
bool verify_complete() {
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            if (board[i][j] == 0) return false;
        }
    }
    return true;
}

// 深さ優先探索
// pos: 現在処理中のフラットなインデックス (0〜8)
// curr_step: 累積操作回数
void explore(int pos, int curr_step) {
    // 終端条件：9マスのすべてを評価済み
    if (pos == 9) {
        if (verify_complete()) {
            min_ops = min(min_ops, curr_step);
        }
        return;
    }

    // 現在の座標に変換
    int r = pos / 3 + 1;
    int c = pos % 3 + 1;

    // パターンA：現在セルを操作せず次へ遷移
    explore(pos + 1, curr_step);

    // パターンB：現在セルを操作し、次へ遷移してから状態を戻す（バックトラック）
    invert_switch(r, c);
    explore(pos + 1, curr_step + 1);
    invert_switch(r, c);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            cin >> board[i][j];
        }
    }

    explore(0, 0);
    cout << min_ops << "\n";

    return 0;
}