网站建设咨询问卷,网络营销的方式包括,网络规划设计师教程(第2版),做银行流水网站费解的开关
joyoi-tyvj 1266
题目大意#xff1a;
有5*5的一个图#xff0c;每个点的数值是1或0#xff0c;如果将一个点的数值取反#xff0c;那这个点上下左右的点都会取反#xff0c;现在问你将所有点都变为1最少要多少步#xff0c;如果步数大于6或无法全变成1的话…费解的开关
joyoi-tyvj 1266
题目大意
有5*5的一个图每个点的数值是1或0如果将一个点的数值取反那这个点上下左右的点都会取反现在问你将所有点都变为1最少要多少步如果步数大于6或无法全变成1的话就输出-1有n组数据
输入样例
3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111输出样例
3
2
-1解题思路
首先我们可以发现一个点取反两次和没取反是一样的所以我们可以暴力枚举25个点变不变但这样就要o(22525n)o(2^{25}25n)o(22525n)就绝对会炸 然后我们一行一行地来看可以发现如果当前行处理后当前行0的位置下方必须点1的位置下方不能点然后我们就可以只枚举第一行然后剩下的直接算出来最后直接判断最后一行合不合法即可时间复杂度o(2525n)o(2^{5}25n)o(2525n)
代码
#includecstdio
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
int n,ans,a[7][7],b[7][7];
int js()
{int sum0;for (int i1;i5;i)for (int j1;j5;j)b[i][j]a[i][j];//用b来临时计算for (int i1;i4;i)for (int j1;j5;j)if (!b[i][j])//如果是0就下方的数取反{b[i][j]^1;b[i1][j]^1;b[i2][j]^1;b[i1][j-1]^1;b[i1][j1]^1;sum;}for (int i1;i5;i)if (!b[5][i])//不合法return 10;//超过6就可以了return sum;
}
void dfs(int dep,int x)
{if (dep5){ansmin(ans,xjs());//求最小值return;}a[1][dep]^1;//取反a[1][dep-1]^1;a[1][dep1]^1;a[2][dep]^1;dfs(dep1,x1);a[1][dep]^1;//不取反a[1][dep-1]^1;a[1][dep1]^1;a[2][dep]^1;dfs(dep1,x);return;
}
int main()
{scanf(%d,n);for (int t1;tn;t){for (int i1;i5;i)for (int j1;j5;j)scanf(%1d,a[i][j]);//输入一位数ans10;dfs(1,0);printf(%d\n,ans7?ans:(-1));}return 0;
}
