描述

你玩過“拉燈”游戲嗎？25盞燈排成一個5x5的方形。每一個燈都有一個開關，游戲者可以改變它的狀態。每一步，游戲者可以改變某一個燈的狀態。游戲者改變一個燈的狀態會產生連鎖反應：和這個燈上下左右相鄰的燈也要相應地改變其狀態。
我們用數字“1”表示一盞開著的燈，用數字“0”表示關著的燈。下面這種狀態
10111
01101
10111
10000
11011
在改變了最左上角的燈的狀態后將變成：
01111
11101
10111
10000
11011
再改變它正中間的燈后狀態將變成：
01111
11001
11001
10100
11011
給定一些游戲的初始狀態，編寫程序判斷游戲者是否可能在6步以內使所有的燈都變亮。
格式

輸入格式

第一行有一個正整數n，代表數據中共有n個待解決的游戲初始狀態。
以下若干行數據分為n組，每組數據有5行，每行5個字符。每組數據描述了一個游戲的初始狀態。各組數據間用一個空行分隔。
對于30%的數據，n<=5；
對于100%的數據，n<=500。
輸出格式

輸出數據一共有n行，每行有一個小于等于6的整數，它表示對于輸入數據中對應的游戲狀態最少需要幾步才能使所有燈變亮。
對于某一個游戲初始狀態，若6步以內無法使所有燈變亮，請輸出“-1”。
樣例1

樣例輸入1

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
Copy
樣例輸出1

3
2
-1
Copy
限制

各個測試點1s
來源

Matrix67原創
.
.
.
.
.

分析

在這里，我們可以發現，每個位置也就點擊一次，而且，固定第一行后，最多只有一種可行方案。由此，我們可以枚舉第一行的32種情況，之后通過遞推，找到最終狀態，遞推結束，只需檢驗最后一行是否合法即可。
.
.
.
.
.

程序：

#include<iostream> #include<string.h> using namespace std; int a[5][5],b[5][5]; char str[6];void change(int x,int y) {b[x][y]^=1;if (x>0) b[x-1][y]^=1;if (x+1<5) b[x+1][y]^=1;if (y>0) b[x][y-1]^=1;if (y+1<5) b[x][y+1]^=1; }int work(int f1) {int i,j,r=0;for (j=0;j<5;j++){if (f1&(1<<j)){r++;change(0,j);}}for (i=1;i<5;i++){for (j=0;j<5;j++){if (b[i-1][j]==0){if (++r>=7){return 7;}change(i,j);}}}for (j=0;j<5;j++){if (b[4][j]==0){return 7;}}return r; }int main() {int n;cin>>n;for (int w=1;w<=n;w++){int step=99999;for (int i=0;i<5;i++){cin>>str;for (int j=0;j<5;j++)a[i][j]=str[j]-'0';}int j;for (int i=0;i<32;i++){memcpy(b,a,sizeof(b));j=work(i);if (j<step) step=j;}if (step<7) cout<<step<<endl;else cout<<-1<<endl;}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499913.html

總結

以上是生活随笔為你收集整理的Vijos 1197 - 费解的开关的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。