今日学习在线编程题：连锁反应

题目来源：码蹄集

https://matiji.net/exam/brushquestion/118/3181/1DC60EA6DF83A333301CFFE1407FBA59

时间限制：1000ms
内存限制：65535kb

题目描述：W在玩一个5x5的棋盘游戏，棋盘上有25个棋子，棋子有黑白两面，初始棋子无规则的正反放置在棋盘上，白用1表示，黑用0表示；
每一次玩家可以改变一个棋子的正反，但是由于有连锁反应，这个棋子的上下左右4个棋子会跟着转变其正反，即0变1，1变0；
W想要知道需要多少步才能使棋盘上的棋子全部变为1；
但是如果需要的步数超过6步（W没有那么多耐心等你算出来），或者，没有办法使棋子全部变为1，你需要告诉W。

输入格式：第一行有一个正整数n，代表数据中共有n个棋盘游戏的初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个数字0/1。每组数据描述了一个棋盘的初始状态。各组数据间用一个空行分隔。​​​​​​​
输出格式：输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的棋盘状态最少需要几步才能使所有棋子白色的面朝上。
对于某一个棋盘初始状态，若6步以内无法使所有棋子白色的面朝上，请输出“-1”。

输入样例：

2
0 0 1 1 1
0 1 0 1 1
1 0 0 0 1
1 1 0 1 0
1 1 1 0 0

1 1 1 0 1
1 1 1 0 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
输出样例：

3
2

备注：n <= 500

参考程序：

#include
using namespace std;
bool s[7][7]={};
int l[10000]={};
void turn(int a,int b)
{s[a][b]=!s[a][b];s[a][b+1]=!s[a][b+1];s[a][b-1]=!s[a][b-1];s[a-1][b]=!s[a-1][b];s[a+1][b]=!s[a+1][b];
}
int judge(int f)
{for(int i=2;i<=5;i++)for(int j=1;j<=5;j++){if(s[i-1][j]) {f++;turn(i,j);}}for(int i=1;i<=5;i++)if(s[5][i]) return 10000;return f;
}
int main()
{int n;cin>>n;for(int p=1;p<=n;p++){int ans=1000000,d[7][7];char s1[7][7];for(int j=1;j<=5;j++)for(int k=1;k<=5;k++){cin>>s1[j][k];d[j][k]=!(bool)(s1[j][k]-'0');}for(int i=0;i<1<<5;i++){for(int j=1;j<=5;j++)for(int k=1;k<=5;k++)s[j][k]=d[j][k];int f=0;for(int j=0;j<5;j++)if(i>>j&1) {turn(1,j+1);f++;}ans=min(ans,judge(f));}if(ans<=6) l[p]=ans;else l[p]=-1;}for(int i=1;i<=n;i++)cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！