再帰を用いた探索手法

再帰は、探索アルゴリズムの実装において非常に強力なツールです。ここでは、いくつかの基本的な列挙問題を再帰関数で解くテンプレートを示します。

部分集合の列挙 (指数型探索)

N個の要素からなる集合のすべての部分集合を生成します。各要素について「含める」か「含めない」かの2つの選択肢があるため、計算量はO(2^N)となります。

#include <iostream>
#include <vector>
#include <numeric> // for std::iota

// max_element_value: 列挙する要素の最大値 (1からmax_element_valueまでを対象とする)
// current_subset_elements: 現在までに選択された要素を格納するベクタ

std::vector<int> current_subset_elements; // グローバルまたはクラスメンバとして定義
int max_element_value; // グローバルまたはクラスメンバとして定義

void enumerate_subsets(int current_processing_value) {
    // ベースケース: すべての要素について選択が完了した場合
    if (current_processing_value > max_element_value) {
        // 現在の部分集合を出力
        for (int val : current_subset_elements) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
        return;
    }

    // current_processing_value を部分集合に含めない場合
    enumerate_subsets(current_processing_value + 1);

    // current_processing_value を部分集合に含める場合
    current_subset_elements.push_back(current_processing_value);
    enumerate_subsets(current_processing_value + 1);
    current_subset_elements.pop_back(); // バックトラック
}

/*
int main() {
    max_element_value = 3; // 例: 1, 2, 3 の部分集合を生成
    enumerate_subsets(1);
    return 0;
}
*/

順列の生成

N個の要素のすべての順列を生成します。計算量はO(N!)となります。

#include <iostream>
#include <vector>
#include <numeric> // for std::iota

// total_permutation_elements: 順列を生成する要素の数 (例: 1からこの値まで)
// current_permutation_result: 現在までに配置された要素を格納するベクタ
// is_element_used: 各要素が使用済みかどうかを示すブールベクタ

int total_permutation_elements; // グローバルまたはクラスメンバとして定義
std::vector<int> current_permutation_result;
std::vector<bool> is_element_used;

void generate_permutations(int current_depth) {
    // ベースケース: すべての要素が配置された場合
    if (current_depth == total_permutation_elements) {
        for (int val : current_permutation_result) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
        return;
    }

    // 現在の深さ (位置) に配置する要素を選択
    for (int i = 1; i <= total_permutation_elements; ++i) {
        if (!is_element_used[i]) {
            is_element_used[i] = true;
            current_permutation_result[current_depth] = i; // depth は 0-indexed, 要素は 1-indexed
            generate_permutations(current_depth + 1);
            is_element_used[i] = false; // バックトラック
        }
    }
}

/*
int main() {
    total_permutation_elements = 3; // 例: 1, 2, 3 の順列を生成
    current_permutation_result.resize(total_permutation_elements);
    is_element_used.resize(total_permutation_elements + 1, false); // 1-indexed for elements
    generate_permutations(0);
    return 0;
}
*/

組み合わせの生成

N個の要素からK個の要素を選択するすべての組み合わせを生成します。計算量はO(C(N, K))となります。

#include <iostream>
#include <vector>

// num_total_elements: 全要素数 (1からnum_total_elementsまで)
// num_choose: 選択する要素の数
// current_combination: 現在までに選択された要素

int num_total_elements; // グローバルまたはクラスメンバとして定義
int num_choose; // グローバルまたはクラスメンバとして定義
std::vector<int> current_combination;

void generate_combinations_recursive(int start_element) {
    // 枝刈り: 既にnum_choose個以上の要素を選択している、
    // または残りの要素数でnum_choose個に達しない場合
    if (current_combination.size() > num_choose ||
        (num_choose - current_combination.size()) > (num_total_elements - start_element + 1)) {
        return;
    }

    // ベースケース: すべての要素を検討し終えた場合
    if (start_element > num_total_elements) {
        if (current_combination.size() == num_choose) {
            for (int val : current_combination) {
                std::cout << val << " ";
            }
            std::cout << std::endl;
        }
        return;
    }

    // start_element を組み合わせに含める場合
    current_combination.push_back(start_element);
    generate_combinations_recursive(start_element + 1);
    current_combination.pop_back(); // バックトラック

    // start_element を組み合わせに含めない場合
    generate_combinations_recursive(start_element + 1);
}

/*
int main() {
    num_total_elements = 4; // 例: {1, 2, 3, 4}
    num_choose = 2; // 2個選択
    generate_combinations_recursive(1);
    return 0;
}
*/

幅優先探索 (BFS) による最短経路

BFSは、重みなしグラフにおける最短経路や、2次元グリッド上の最短移動経路を見つけるのに適しています。

2次元グリッド上の最短経路

スタート地点からゴール地点までの最短経路の長さを計算します。障害物がある場合や、移動が上下左右に限定される場合によく利用されます。

#include <iostream>
#include <vector>
#include <queue>
#include <tuple> // for std::tuple

struct GridCoordinate {
    int r, c;
};

// グリッドのサイズ
int grid_rows_count, grid_cols_count;
// グリッドデータ (0:道, 1:障害物)
std::vector grid_layout;
// 最短距離を記録 (未訪問: -1)
std::vector shortest_distances;

// 移動方向 (上下左右)
int delta_r[] = {-1, 1, 0, 0};
int delta_c[] = {0, 0, -1, 1};

int calculate_shortest_path_grid(GridCoordinate start_pos, GridCoordinate end_pos) {
    shortest_distances.assign(grid_rows_count, std::vector<int>(grid_cols_count, -1));
    std::queue<GridCoordinate> traversal_queue;

    traversal_queue.push(start_pos);
    shortest_distances[start_pos.r][start_pos.c] = 0;

    while (!traversal_queue.empty()) {
        GridCoordinate current_coord = traversal_queue.front();
        traversal_queue.pop();

        if (current_coord.r == end_pos.r && current_coord.c == end_pos.c) {
            return shortest_distances[current_coord.r][current_coord.c];
        }

        for (int i = 0; i < 4; ++i) {
            int next_r = current_coord.r + delta_r[i];
            int next_c = current_coord.c + delta_c[i];

            // 範囲チェック
            if (next_r < 0 || next_r >= grid_rows_count || next_c < 0 || next_c >= grid_cols_count) {
                continue;
            }
            // 訪問済みまたは障害物チェック
            if (shortest_distances[next_r][next_c] != -1 || grid_layout[next_r][next_c] == 1) {
                continue;
            }

            shortest_distances[next_r][next_c] = shortest_distances[current_coord.r][current_coord.c] + 1;
            traversal_queue.push({next_r, next_c});
        }
    }
    return -1; // ゴールに到達できない場合
}

/*
int main() {
    grid_rows_count = 3; grid_cols_count = 3;
    grid_layout = {{0, 0, 0},
                   {0, 1, 0},
                   {0, 0, 0}};
    
    GridCoordinate start_node = {0, 0};
    GridCoordinate end_node = {2, 2};
    int path_len = calculate_shortest_path_grid(start_node, end_node);
    if (path_len != -1) {
        std::cout << "最短経路の長さ: " << path_len << std::endl;
    } else {
        std::cout << "到達不可能" << std::endl;
    }
    return 0;
}
*/

グラフ (または木) のノードレベル探索

グラフの特定のノードから他のノードへの最短ホップ数 (エッジ数) を計算します。これは、グラフの各ノードの「レベル」を見つけるのに使われます。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // for std::fill

// graph_adjacency_list: 隣接リスト (グラフの表現)
// node_depths: 各ノードの開始ノードからのレベル (距離) を記録
// total_graph_nodes: グラフのノード数

std::vector graph_adjacency_list;
std::vector<int> node_depths;
int total_graph_nodes;

int compute_node_depths(int initial_node) {
    node_depths.assign(total_graph_nodes + 1, -1); // -1で未訪問を示す
    std::queue<int> bfs_queue;

    bfs_queue.push(initial_node);
    node_depths[initial_node] = 0;

    while (!bfs_queue.empty()) {
        int current_vertex = bfs_queue.front();
        bfs_queue.pop();

        for (int neighbor_vertex : graph_adjacency_list[current_vertex]) {
            if (node_depths[neighbor_vertex] == -1) { // 未訪問の場合
                node_depths[neighbor_vertex] = node_depths[current_vertex] + 1;
                bfs_queue.push(neighbor_vertex);
            }
        }
    }
    // 例として、ターゲットとなるノード（ここでは最後のノード）までの距離を返す
    return node_depths[total_graph_nodes]; 
}

/*
int main() {
    total_graph_nodes = 5;
    graph_adjacency_list.resize(total_graph_nodes + 1);
    graph_adjacency_list[1] = {2, 3};
    graph_adjacency_list[2] = {1, 4};
    graph_adjacency_list[3] = {1, 5};
    graph_adjacency_list[4] = {2};
    graph_adjacency_list[5] = {3};

    std::cout << "ノード 1 からノード 5 への最短ホップ: " << compute_node_depths(1) << std::endl;
    return 0;
}
*/

深さ優先探索 (DFS) による連結性判定

DFSは、グラフやグリッドの連結性を調べるために頻繁に使用されます。ある2点間が到達可能か、または連結成分の数を数える際に応用されます。

2点間の到達可能性判定

ある開始点から特定の目的点まで到達可能かどうかを判断します。

#include <iostream>
#include <vector>
#include <string>

// グリッドのサイズ
int map_rows, map_cols;
// グリッドデータ ('#':障害物, '.':道)
std::vector game_map;
// 訪問済みフラグ
std::vector visited_map_cells;

// 目的座標
int target_row_coord, target_col_coord;

// 移動方向 (上下左右)
int dr_move[] = {-1, 1, 0, 0};
int dc_move[] = {0, 0, -1, 1};

bool check_reachability(int current_r, int current_c) {
    visited_map_cells[current_r][current_c] = true;

    if (current_r == target_row_coord && current_c == target_col_coord) {
        return true;
    }

    for (int i = 0; i < 4; ++i) {
        int next_r = current_r + dr_move[i];
        int next_c = current_c + dc_move[i];

        // 範囲チェック
        if (next_r < 0 || next_r >= map_rows || next_c < 0 || next_c >= map_cols) {
            continue;
        }
        // 訪問済みまたは障害物チェック
        if (visited_map_cells[next_r][next_c] || game_map[next_r][next_c] == '#') {
            continue;
        }

        if (check_reachability(next_r, next_c)) {
            return true;
        }
    }
    return false;
}

/*
int main() {
    map_rows = 3; map_cols = 3;
    game_map = {"...",
                ".#.",
                "..."};
    visited_map_cells.assign(map_rows, std::vector<bool>(map_cols, false));
    
    target_row_coord = 2; target_col_coord = 2;
    if (check_reachability(0, 0)) {
        std::cout << "到達可能" << std::endl;
    } else {
        std::cout << "到達不可能" << std::endl;
    }
    return 0;
}
*/

連結成分の数の計算

グリッド内の「道」を示すセルがいくつ連結した塊 (連結成分) を形成しているかを数えます。これは島問題などでよく見られます。

#include <iostream>
#include <vector>
#include <string>

// グリッドのサイズ
int component_grid_height, component_grid_width;
// グリッドデータ ('#':障害物, '.':道)
std::vector component_grid_data;
// 訪問済みフラグ
std::vector component_grid_visited;

// 移動方向 (8方向)
int eight_dir_r[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int eight_dir_c[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void dfs_explore_component(int r_coord, int c_coord) {
    component_grid_visited[r_coord][c_coord] = true;

    for (int i = 0; i < 8; ++i) { // 8方向探索
        int next_r = r_coord + eight_dir_r[i];
        int next_c = c_coord + eight_dir_c[i];

        if (next_r < 0 || next_r >= component_grid_height || next_c < 0 || next_c >= component_grid_width) {
            continue;
        }
        if (component_grid_visited[next_r][next_c] || component_grid_data[next_r][next_c] == '#') {
            continue;
        }
        dfs_explore_component(next_r, next_c);
    }
}

/*
int main() {
    component_grid_height = 3; component_grid_width = 4;
    component_grid_data = {".##.",
                           "..#.",
                           ".#.."};
    component_grid_visited.assign(component_grid_height, std::vector<bool>(component_grid_width, false));
    
    int total_connected_components = 0;
    for (int i = 0; i < component_grid_height; ++i) {
        for (int j = 0; j < component_grid_width; ++j) {
            if (component_grid_data[i][j] == '.' && !component_grid_visited[i][j]) {
                dfs_explore_component(i, j);
                total_connected_components++;
            }
        }
    }
    std::cout << "連結成分の数: " << total_connected_components << std::endl;
    return 0;
}
*/

深さ優先探索 (DFS) による木の直径の計算

木の直径とは、木の中で最も遠い2つのノード間のパスの長さ (エッジの重みの合計) です。これは2回のDFSで効率的に計算できます。

#include <iostream>
#include <vector>
#include <algorithm> // for std::max

struct WeightedEdge {
    int target_node;
    int edge_weight;
};

// グラフの隣接リスト
std::vector tree_graph_adj;
// 各ノードへのパス長
std::vector<long long> current_path_lengths;
// 直径の端点の一つを記録
int one_farthest_node_index;

// DFS関数: 現在のノードu、親ノードp
void find_farthest_node(int u, int p) {
    for (const auto& edge : tree_graph_adj[u]) {
        int v = edge.target_node;
        int w = edge.edge_weight;
        if (v == p) {
            continue;
        }
        current_path_lengths[v] = current_path_lengths[u] + w;
        // 最も遠いノードを更新
        if (current_path_lengths[v] > current_path_lengths[one_farthest_node_index]) {
            one_farthest_node_index = v;
        }
        find_farthest_node(v, u);
    }
}

/*
int main() {
    int total_nodes_in_tree;
    std::cin >> total_nodes_in_tree;

    tree_graph_adj.resize(total_nodes_in_tree + 1);
    for (int i = 0; i < total_nodes_in_tree - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        tree_graph_adj[u].push_back({v, w});
        tree_graph_adj[v].push_back({u, w});
    }

    current_path_lengths.assign(total_nodes_in_tree + 1, 0);
    one_farthest_node_index = 1; // 任意のノードからDFSを開始
    find_farthest_node(1, 0); // 1回目のDFSで、ある端点を見つける

    current_path_lengths.assign(total_nodes_in_tree + 1, 0); // 距離をリセット
    // 1回目で見つけた端点から再度DFS
    find_farthest_node(one_farthest_node_index, 0); // 2回目のDFSで、直径の長さと反対側の端点を見つける
    
    std::cout << "木の直径: " << current_path_lengths[one_farthest_node_index] << std::endl;
    return 0;
}
*/

深さ優先探索 (DFS) による木の重心の探索

木の重心とは、そのノードを根としたときに、最も大きい部分木のサイズが最小になるノードのことです。重心を削除すると、木は最大でも元のサイズの半分以下の部分木に分割されます。

#include <iostream>
#include <vector>
#include <algorithm> // for std::max, std::min

// グラフの隣接リスト
std::vector centroid_tree_adj;
// 訪問済みフラグ
std::vector<bool> centroid_visited_flags;
// 全ノード数
int total_nodes_for_centroid;
// 最小の最大部分木サイズを記録
int min_max_component_size = 1e9; // 十分大きな値で初期化
// 重心ノードを格納 (複数存在する場合もあるが、ここでは代表として1つ)
std::vector<int> tree_centroids;

// DFS関数: 現在のノードu
// 戻り値: uを根とする部分木のサイズ
int calculate_subtree_size_and_find_centroid(int u) {
    centroid_visited_flags[u] = true;
    int subtree_node_count = 1; // 自分自身を含む
    int max_child_component_size = 0; // 子の部分木の最大サイズ

    for (int v : centroid_tree_adj[u]) {
        if (!centroid_visited_flags[v]) {
            int child_component_size = calculate_subtree_size_and_find_centroid(v);
            max_child_component_size = std::max(max_child_component_size, child_component_size);
            subtree_node_count += child_component_size;
        }
    }

    // uを削除したときに、上方向 (親側) に残る部分木のサイズ
    int remaining_tree_upwards_size = total_nodes_for_centroid - subtree_node_count;
    max_child_component_size = std::max(max_child_component_size, remaining_tree_upwards_size);

    // 重心条件を更新
    if (max_child_component_size < min_max_component_size) {
        min_max_component_size = max_child_component_size;
        tree_centroids.clear(); // より良い重心が見つかったのでクリア
        tree_centroids.push_back(u);
    } else if (max_child_component_size == min_max_component_size) {
        tree_centroids.push_back(u);
    }
    
    return subtree_node_count;
}

/*
int main() {
    total_nodes_for_centroid = 6;
    centroid_tree_adj.resize(total_nodes_for_centroid + 1);
    centroid_tree_adj[1] = {2, 3};
    centroid_tree_adj[2] = {1, 4};
    centroid_tree_adj[3] = {1, 5, 6};
    centroid_tree_adj[4] = {2};
    centroid_tree_adj[5] = {3};
    centroid_tree_adj[6] = {3};

    centroid_visited_flags.assign(total_nodes_for_centroid + 1, false);
    calculate_subtree_size_and_find_centroid(1); // 任意のノードからDFSを開始

    std::cout << "木の重心: ";
    for (int c_node : tree_centroids) {
        std::cout << c_node << " ";
    }
    std::cout << " (最大部分木サイズ: " << min_max_component_size << ")" << std::endl;
    return 0;
}
*/

バックトラッキング (再帰的探索と枝刈り)

バックトラッキングは、すべての可能な解候補を探索するアルゴリズムで、解が見つからないパスを進んだときに「引き返す」ことで効率を上げます。枝刈り (Pruning) は、解に繋がらないことが確定したパスを早期に打ち切る最適化手法です。

バックトラッキングの例: ナイトツアー問題

チェス盤上のナイトが、すべてのマスを一度ずつ訪れる経路を見つける問題です。

#include <iostream>
#include <vector>

// チェス盤のサイズ
int board_rows_dims, board_cols_dims;
// 訪問済みフラグ
std::vector visited_board_cells;
// 有効なナイトツアーの総数
long long total_knight_tours = 0;

// ナイトの移動方向 (8方向)
int knight_move_dr[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int knight_move_dc[] = {-1, 1, -2, 2, -2, 2, -1, 1};

void find_all_knight_tours(int current_r, int current_c, int cells_visited_count) {
    // ベースケース: すべてのマスを訪問した場合
    if (cells_visited_count == board_rows_dims * board_cols_dims) {
        total_knight_tours++;
        return;
    }

    // 次の移動を試す
    for (int i = 0; i < 8; ++i) {
        int next_r = current_r + knight_move_dr[i];
        int next_c = current_c + knight_move_dc[i];

        // 範囲チェック
        if (next_r < 0 || next_r >= board_rows_dims || next_c < 0 || next_c >= board_cols_dims) {
            continue;
        }
        // 訪問済みチェック
        if (visited_board_cells[next_r][next_c]) {
            continue;
        }

        visited_board_cells[next_r][next_c] = true; // 訪問マーク
        find_all_knight_tours(next_r, next_c, cells_visited_count + 1);
        visited_board_cells[next_r][next_c] = false; // バックトラック (訪問マークを解除)
    }
}

/*
int main() {
    board_rows_dims = 5; // 5x5盤
    board_cols_dims = 5;
    visited_board_cells.assign(board_rows_dims, std::vector<bool>(board_cols_dims, false));

    // 開始地点 (例: 0,0) から探索を開始
    visited_board_cells[0][0] = true;
    find_all_knight_tours(0, 0, 1);
    visited_board_cells[0][0] = false; // 後処理

    std::cout << "可能なナイトツアーの総数: " << total_knight_tours << std::endl;
    return 0;
}
*/

枝刈りDFSの例: 猫の荷物積み込み問題

複数の猫 (それぞれ異なる重さ) を、容量Wの複数の籠に積むとき、必要な籠の最小数を求めます。ここで重要なのは、現在の探索で既に最適な解よりも多くの籠を使っている場合、そのパスは探索を中止できるという枝刈りです。

#include <iostream>
#include <vector>
#include <algorithm> // for std::min, std::sort
#include <functional> // for std::greater

// 猫の数と籠の最大容量
int number_of_cats;
int maximum_basket_capacity;
// 猫の重さのリスト
std::vector<int> cat_weights_list;
// 各籠の現在の積載量
std::vector<int> basket_current_loads;
// 必要な籠の最小数
int minimum_baskets_required;

// DFS関数: 現在処理中の猫のインデックスcat_index、現在使用中の籠の数baskets_in_use
void solve_cat_loading_problem(int cat_index, int baskets_in_use) {
    // 枝刈り: 既に最適な解よりも多くの籠を使っている場合
    if (baskets_in_use >= minimum_baskets_required) {
        return;
    }
    // ベースケース: すべての猫を配置し終えた場合
    if (cat_index == number_of_cats) {
        minimum_baskets_required = std::min(minimum_baskets_required, baskets_in_use);
        return;
    }

    // オプション1: 既存の籠に猫を積むことを試みる
    for (int i = 0; i < baskets_in_use; ++i) {
        if (basket_current_loads[i] + cat_weights_list[cat_index] <= maximum_basket_capacity) {
            basket_current_loads[i] += cat_weights_list[cat_index]; // 積む
            solve_cat_loading_problem(cat_index + 1, baskets_in_use);
            basket_current_loads[i] -= cat_weights_list[cat_index]; // バックトラック (元に戻す)
        }
    }

    // オプション2: 新しい籠に猫を積む
    // 新しい籠を使うのは、既存の籠に積めなかった場合、または新しい籠が必要な場合
    // ただし、新しい籠は `baskets_in_use` 番目の籠として考える
    // `baskets_in_use` は0-indexedで、`baskets_in_use` 番目の籠はまだ使われていないので新しい籠とみなせる。
    // この新しい籠に積むのは、まだ容量を超えていない場合のみ考慮する
    if (baskets_in_use < number_of_cats) { // 籠の総数は猫の数を超えない
      basket_current_loads[baskets_in_use] += cat_weights_list[cat_index]; // 新しい籠に積む
      solve_cat_loading_problem(cat_index + 1, baskets_in_use + 1);
      basket_current_loads[baskets_in_use] -= cat_weights_list[cat_index]; // バックトラック
    }
}

/*
int main() {
    number_of_cats = 5;
    maximum_basket_capacity = 10;
    cat_weights_list = {2, 3, 4, 5, 6}; // 猫の重さ
    
    // 最適化: 重い猫から順に配置することで、より早く枝刈りが効く可能性がある
    std::sort(cat_weights_list.begin(), cat_weights_list.end(), std::greater<int>());

    minimum_baskets_required = number_of_cats; // 最悪の場合、猫の数と同じ数の籠が必要
    basket_current_loads.assign(number_of_cats, 0); // 籠の数は最大でも猫の数まで
    
    solve_cat_loading_problem(0, 0); // 0番目の猫から、0個の籠を使って開始

    std::cout << "必要な籠の最小数: " << minimum_baskets_required << std::endl;
    return 0;
}
*/
```

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // for std::min

// グリッドのサイズは固定で5x5
const int BOARD_DIM = 5;
// グリッドの状態 ('0':消灯, '1':点灯)
std::vector current_board_lights;
std::vector initial_board_state; // 状態を保存するためのバックアップ

// クリックによる状態変化の方向 (自己 + 上下左右)
int toggle_dr[] = {0, -1, 1, 0, 0};
int toggle_dc[] = {0, 0, 0, -1, 1};

// 指定された座標(r, c)の照明とその隣接照明の状態を反転させる
void perform_toggle(int r, int c) {
    for (int i = 0; i < 5; ++i) { // 5方向 (自己+上下左右)
        int nr = r + toggle_dr[i];
        int nc = c + toggle_dc[i];

        if (nr >= 0 && nr < BOARD_DIM && nc >= 0 && nc < BOARD_DIM) {
            current_board_lights[nr][nc] = (current_board_lights[nr][nc] == '0' ? '1' : '0');
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false); // C++標準ストリームの高速化
    std::cin.tie(NULL);

    int test_case_count;
    std::cin >> test_case_count;

    while (test_case_count--) {
        current_board_lights.resize(BOARD_DIM);
        for (int i = 0; i < BOARD_DIM; ++i) {
            std::cin >> current_board_lights[i];
        }
        initial_board_state = current_board_lights; // 初期状態を保存

        int overall_min_presses = 1e9; // 非常に大きな値で初期化

        // 最初の行の2^BOARD_DIM通りの操作パターンを全て試す (ビットマスク operation_mask)
        for (int operation_mask = 0; operation_mask < (1 << BOARD_DIM); ++operation_mask) {
            current_board_lights = initial_board_state; // 毎回初期状態に戻す
            int presses_for_this_mask = 0;

            // 最初の行の操作を実行
            for (int col = 0; col < BOARD_DIM; ++col) {
                if ((operation_mask >> col) & 1) { // col番目のビットが立っていれば操作
                    perform_toggle(0, col);
                    presses_for_this_mask++;
                }
            }

            // 2行目から最終行まで、上の行の消灯状態に基づいて操作を決定
            for (int r = 0; r < BOARD_DIM - 1; ++r) {
                for (int c = 0; c < BOARD_DIM; ++c) {
                    if (current_board_lights[r][c] == '0') { // 上の行の照明が消えていない場合
                        perform_toggle(r + 1, c); // その下の照明を操作する
                        presses_for_this_mask++;
                    }
                }
            }

            // 最終行がすべて消灯しているかを確認
            bool is_all_off_in_last_row = true;
            for (int col = 0; col < BOARD_DIM; ++col) {
                if (current_board_lights[BOARD_DIM - 1][col] == '0') {
                    is_all_off_in_last_row = false;
                    break;
                }
            }

            if (is_all_off_in_last_row) {
                overall_min_presses = std::min(overall_min_presses, presses_for_this_mask);
            }
        }

        // 問題の制約による (例: 6回以下で解けるか)
        if (overall_min_presses > 6) { 
            std::cout << -1 << std::endl;
        } else {
            std::cout << overall_min_presses << std::endl;
        }
    }
    return 0;
}
```