再帰アルゴリズム: 不可解なスイッチ「ライトを引く」

[[411620]]

タイトル出典：AcWing[1]。

トピック

「Pull the Light」というゲームをしたことがありますか?

ライトは正方形に配置されています。

各ライトには、プレイヤーが状態を変更するために使用できるスイッチがあります。

各ステップで、プレイヤーは特定のライトの状態を変更できます。

プレイヤーがライトの状態を変更すると、連鎖反応が発生し、このライトの上、下、左、右に隣接するライトの状態もそれに応じて変化します。

点灯しているライトを表すには数字を使用し、消灯しているライトを表すには数字を使用します。

次の状態

左上隅のライトの状態を変更すると、次のようになります。

真ん中のライトを変更すると、ステータスは次のようになります。

ゲームの初期状態がいくつか与えられた場合、プレイヤーがステップ内ですべてのライトを明るくすることが可能かどうかを判断するプログラムを作成します。

入力フォーマット

入力の最初の行は正の整数です。これは、データ内に解決すべき初期ゲーム状態の合計があることを意味します。

次のデータ行はグループに分かれており、各データグループには行があり、各行には文字があります。

各データセットはゲームの初期状態を表します。

各データグループは空白行で区切られます。

出力フォーマット

合計で行のデータが出力され、各行には未満の整数が含まれます。これは、入力データ内の対応するゲーム状態ですべてのライトを点灯させるために必要な最小ステップ数を表します。

ゲームの特定の初期状態で、ステップ内ですべてのライトを明るくできない場合は出力します。

データ範囲

サンプル入力:

サンプル出力:

 3
 2
 -1

解決

まず、説明する必要がある 3 つの非常に重要な特性があります。

ライトを押す場合、どの順番で押しても問題ありません。どの順番で押しても結果は同じです。
ライトを 2 回以上押す必要はありません。2 回押すと押さないのと同じになり、3 回押すと 2 回 + 1 回 (つまり 1 回) 押すのと同じになります。

したがって：

ライトを押す順序は重要ではないので、最初に最初の行にあるライトをすべて押すことができます。
最初の列のすべてのライトを押した後、最初の列のすべてのライトを点灯させたい場合、最初の列の点灯していないライトの下にあるライトのみを押すことができることがわかりました（以下は例です）

最初の行のステータスは 10011 です (1 はライトが点灯していることを示します)
 2行目のアクション01100（1はボタンを押すことを表す）

では、2 列目が完全に点灯していることをどのように確認するのでしょうか? この問題を解決するには、3 列目を使用するしかありません。

では、最後の列 (5 列目) が完全に点灯していることをどうやって確認するのでしょうか? それを確認する方法はありません。

1 列目の押し方が決まると、次の 2 列目、3 列目、4 列目、5 列目の押し方と、すべて点灯できるかどうかが決まることがわかりました。

したがって、任意の入力状態について、最初の行の 32 個のメソッドすべてを走査して、どのメソッドが完全に点灯できるか (5 行目の状態をチェックすることによって)、またこれらの完全に点灯しているメソッドのいずれかの操作数が 6 以下であるかどうかを確認します。はいの場合はオペランドを返し、そうでない場合は -1 を返します。

コード

#include <iostream>
 #include <cstring>
 #include <アルゴリズム>
名前空間 std を使用します。 
 
 const int N = 5 + 5; // セキュリティ強化のため 5 を加算
// 入力ストリームの各行にはスペースがないので、受信時に文字列を使用する方が便利であることに注意してください。
 char g[N][N]; // ライトの現在の状態を記録する
 
 // 右上、左下、中央
整数dx[5] = {0, 1, 0, -1, 0};
 dy [5] = {1, 0, -1, 0, 0}; 
 
 // x 行目と y 列目に従って、上下左右の 5 つのライトを反転します。
 void 回転( int x, int y)
 {
 ( int i = 0; i < 5; ++ i)の場合
    {
 int a = x + dx[i]、b = y + dy[i];
        （0 <= a && a < 5 && 0 <= b && b < 5）の場合
            g[a][b] = g[a][b] == '1' ? '0' : '1' ;
    }
 } 
 
整数 仕事（）
 {
整数ans = 2e9;
    // 最初のループ、最初の行の押下をすべて走査します
    // kは圧縮状態であり、最小値0b00000は押されていないことを意味します。
    // 最大値0b11111はすべての押下を表します
     
    // バックアップ。次の操作によりgが変更されるため
charバックアップ[N][N];
    memcpy(バックアップ、g、gのサイズ); 
 
 ( int k = 0; k < (1 << 5); ++ k)の場合
    {
        // gが入力gであることを確認する
        memcpy(g, バックアップ, バックアップのサイズ); 
 
        // 最初の行が k の場合、操作の合計数は..
 int res = 0; // resを使用して記録する
 
        // k を実行します (k に応じて最初の行を押します)
 ( int j = 0; j < 5; ++ j)の場合
        {
            (k >> j & 1) の場合
            {
                解像度++;
                ターン(0, j);
            }
        } 
         
        // 最初の行は確定し、2行目は確定する
        // 2行目だけが妥当なので
        // 最初の行を点灯する
        // 同様に、2行目が決定された後、3行目は2行目によって決定されます
( int i = 0; i < 4; ++ i)の場合
        {
 ( int j = 0; j < 5; ++ j)の場合
            {
                g[i][j] == '0'の場合
                {
                    解像度++;
                    ターン(i + 1, j);
                }
            }
        } 
 
        // 上記の操作により、最初の4行がすべて明るくなります
        // ただし、5 列目は必ずしも完全に点灯する必要はありません。5 列目が完全に点灯している場合にのみ、操作が真に効果的になります。
        ブール成功 = true ;
 ( int j = 0; j < 5; ++ j)の場合
        {
            g[4][j] == '0'の場合
            {
                成功 = false ;
                壊す;
            }
        } 
         
        // 有効な操作であれば、スイッチが何回押されたかを確認します
        if (成功) ans = min (res, ans);
    } 
     
    // 質問に応じて出力値を返します
    答えが 6 より大きい場合は-1 を返します。
回答を返す;
 } 
 
 intメイン()
 {
整数n;
    cin >> n;
    (n -- ) の間 
    {
 ( int i = 0; i < 5; ++ i) cin >> g[i] ;
        printf( "%d\n" , work ());
    }
 }