アルゴリズム:難解なスイッチ(プッシュと再帰)

本題の考え方
この問題は私たちが遊んだ小さなゲームに似ています.中間ボタンを押すと、このボタンと上下左右4方向のランプのスイッチが1回切り替わります.この問題では、マトリクス全体を6ステップ以内に点灯できるかどうかを要求します.実はこの問題の構想はとても“清奇”で、私達が第1行のすべての操作を遍歴して(全部で2^5種類の情況があります)それから第1行の明かりをすべて点灯するため、第2行の操作は第1行の明かりの状態によって唯一確定することができます.このようにして、次のすべての操作を決定することができます.最後の行が明るいかどうかを気にするだけです.最後の行を除く位置は必ず明るいからです.
問題の説明
「明かりを引く」ゲームをしたことがありますか.25個のランプが5 x 5の四角に並んでいます.各ランプにはスイッチがあり、プレイヤーはその状態を変えることができます.一歩一歩、ゲーム者はランプの状態を変えることができます.ゲーム者が1つのランプの状態を変えると、連鎖反応が発生します.このランプの上下左右に隣接するランプもそれに応じて状態を変えなければなりません.
私たちは数字「1」で点灯しているランプを表し、数字「0」で消灯しているランプを表します.次のような状態
10111 01101 10111 10000 11011最左上隅のランプの状態を変更すると、
01111 11101 10111 10000 11011真ん中のランプを変更すると、次の状態になります.
01111 11001 11001 10100 11011は、いくつかのゲームの初期状態を与え、作成プログラムは、ゲーム者が6ステップ以内にすべてのランプを点灯させる可能性があるかどうかを判断する.
入力フォーマット
最初の行は正の整数nを入力し、データの中にn個の解決すべきゲームの初期状態があることを表す.
以下のいくつかの行のデータはnグループに分けられ、各グループのデータは5行あり、各行は5文字である.各グループのデータは、ゲームの初期状態を記述する.各グループのデータ間は空の行で区切られます.
出力フォーマット
合計n行のデータが出力され、各行には6以下の整数があり、入力データに対応するゲーム状態に対して少なくとも数ステップですべてのランプを点灯させる必要があることを示しています.
あるゲームの初期状態について、6ステップ以内ですべてのランプを点灯させることができない場合は"-1"を出力します.
データ範囲
0
サンプルを入力:
3 00111 01011 10001 11010 11100
11101 11101 11110 11111 11111
01111 11111 11111 11111 11111
出力サンプル:
3 2 -1
コード#コード#

#include
using namespace std;
int map[10][10];
int map1[10][10];
int dir[5][2] = {
     -1, 0, 0, 0, 1, 0, 0, -1, 0, 1};

void turn(int x, int y){
     
    for(int i = 0; i < 5; ++i){
     
        int a = dir[i][0] + x;
        int b = dir[i][1] + y;
        if(a < 0 || a >= 5 || b < 0 || b >= 5){
     
            continue;
        }else{
     
            map1[a][b] = -map1[a][b];
        }
    }
}

int main(){
     
    int n;
    cin >> n;
    getchar();
    while(n--){
     
        for(int i = 0; i < 5; ++i){
     
            for(int j = 0; j < 5; ++j){
     
                char c;
                scanf("%c", &c);
                if(c == '1'){
     
                    map1[i][j] = 1;
                    map[i][j] = 1;    
                }else{
     
                    map1[i][j] = map[i][j] = -1;
                }
            }
            getchar();
        }
        int cnt = 26;
        for(int i = 0; i < 32; ++i){
     
            int opera = 0;
            for(int i = 0; i < 5; ++i){
     
                for(int j = 0; j < 5; ++j){
     
                    map1[i][j] = map[i][j];
                }
            }
            for(int j = 0; j < 5; ++j)
                if(i >> j & 1){
     
                    turn(0, j);
                    opera++;
                }
            for(int j = 0; j < 4; ++j)
                for(int k = 0; k < 5; ++k)
                    if(map1[j][k] == -1){
     
                        turn(j+1, k);
                        opera++;
                    }
            int dark = 0;
            for(int j = 0; j < 5; ++j){
     
                if(map1[4][j] == -1){
     
                    dark = 1;
                    break;
                }
            }
            if(dark == 0){
     
                cnt = min(cnt, opera);
            }
        }
        if(cnt > 6){
     
            cout << -1 << endl;
        }else{
     
            cout << cnt << endl;
        }
        getchar();
    }
    return 0;
}

原題リンク