不同类型网站比较,查找网站备案,推广网站怎样阻止,永登网站设计与建设题目描述
你玩过“拉灯”游戏吗#xff1f;2525盏灯排成一个5x55x5的方形。每一个灯都有一个开关#xff0c;游戏者可以改变它的状态。每一步#xff0c;游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应#xff1a;和这个灯上下左右相邻的灯也要相应…题目描述
你玩过“拉灯”游戏吗2525盏灯排成一个5x55x5的方形。每一个灯都有一个开关游戏者可以改变它的状态。每一步游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字“11”表示一盏开着的灯用数字“00”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011Copy
在改变了最左上角的灯的状态后将变成
01111
11101
10111
10000
11011Copy
再改变它正中间的灯后状态将变成
01111
11001
11001
10100
11011Copy
给定一些游戏的初始状态编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
样例输入
第一行有一个正整数nn代表数据中共有nn个待解决的游戏初始状态。 以下若干行数据分为nn组每组数据有55行每行55个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
样例输出
输出数据一共有nn行每行有一个小于等于66的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态若6步以内无法使所有灯变亮请输出“-1−1”。
样例
样例一
输入数据 1
3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111Copy
输出数据 1
3
2
-1Copy
数据范围
30\%pts: n \le 530%pts:n≤5
100\%pts: n \le 500。100%pts:n≤500。 代码:
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;
const int N 6;//开六个防止边缘的按钮越界 char game[N][N], backup[N][N];void turn(int x, int y){//使用异或进行五个按钮反转处理 game[x][y] ^ 1;game[x-1][y] ^ 1;game[x][y-1] ^ 1;game[x][y1] ^ 1;game[x1][y] ^ 1;
}int main(){int n;cin n;while(n--){for(int i 0; i 5; i) cin game[i];int result 0x3f3f3f;for(int op 0; op 31; op ){//对第一行的所有按动方式进行枚举memcpy(backup, game, sizeof(game));int step 0;for(int i 0; i 5; i){if(op i 1){// 数字2 对应了00010表示第二个位置按一下//数字3 对应了00011 表示第1 和第2个位置的按一下 step;turn(0,i);} } for(int i 1; i 5; i){for(int j 0; j 5; j){if(game[i-1][j] 0 ){step;turn(i, j);}}}bool success true;for(int i 0; i 5; i){if(game[4][i] 0){success false;break;}}if(success){result min(result, step);}memcpy(game, backup, sizeof(game));}//最后判断是否大于六步因为在32中操作中如果当前的大于6步后面有不大于6步的就没办法有效利用了 if(result 6) result -1; // 大于六步输出-1 printf(%d\n, result);}return 0;
}
