CH0201 费解的开关

描述

你玩过“拉灯”游戏吗？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”。

样例输入

样例输出

3
2
-1

 1 #include
 2 using namespace std;
 3 int f[5][5],tmp[5][5],dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};
 4 void turn(int x,int y)
 5 {
 6     for(int k=0;k<5;k++)
 7     {
 8         int a=x+dx[k],b=y+dy[k];
 9         if(a>=0&&a<5&&b>=0&&b<5)
10         f[a][b]^=1;
11     }
12 }
13 int dfs(int row,int use)
14 {
15     if(use>6)return -1;
16     if(row==4)
17     {
18         for(int j=0;j<5;j++)if(f[4][j]==0)return -1;
19         return use;
20     }
21     
22     for(int j=0;j<5;j++)
23     if(f[row][j]==0)
24     {
25         turn(row+1,j);
26         use++;
27     }
28     return dfs(row+1,use);
29 }
30 int main()
31 {
32     int T;
33     cin>>T;
34     while(T--)
35     {
36         int ans=INT_MAX;
37         for(int i=0;i<5;i++)    
38         for(int j=0;j<5;j++)
39         {
40             char ch;
41             cin>>ch;
42             f[i][j]=ch^48;
43         }    
44         for(int i=0;i<1<<5;i++)
45         {
46             memcpy(tmp,f,sizeof(tmp));
47             int cnt=0;
48             for(int j=0;j<5;j++)
49             if(i>>j&1)
50             {
51                 turn(0,j);
52                 cnt++;
53             }
54             int t=dfs(0,cnt);
55             memcpy(f,tmp,sizeof(f));
56             if(t==-1)continue;
57             else ans=min(ans,t);        
58         }
59         if(ans==INT_MAX)puts("-1");
60         else printf("%d\n",ans);
61         
62     }
63     
64     return 0;
65 }

算法进阶指南

CH0201 费解的开关

描述

输入格式

输出格式

样例输入

样例输出

相关

标签