题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <string.h>
using namespace std;
char matrix[6][6];
char g[6][6];
int dx[5]={1,-1,0,0,0},dy[5]={0,0,-1,1,0};
// int cnt = 0;//计数
void turn(int a,int b,int *cnt)
{
// cout << a<<" "<<b+1<<endl;
*cnt+=1;
// cout << *cnt<<endl;
for(int i = 0;i < 5;i++)
{
int x = a+dx[i];
int y = b+dy[i];
// cout << x <<" "<<y<<endl;
if(y<0||y>4)continue;
matrix[x][y]^=1;
}
// for(int i = 1; i<=5;i++)
// cout << matrix[i]<<endl;
}
int main()
{
int n;
cin >> n;
int H[37];
for(int i = 0;i < 36;i++)H[(1ll<<i)%37] = i;
while(n--)
{
for(int i = 1;i <= 5;i++)scanf("%s",g[i]);
memcpy(matrix,g,sizeof(g));
int res = 0x3f3f3f3f;
for(int i = 0;i < 1<<5;i++)
{
int cnt = 0;
// cout << endl<<"i:"<<i<<endl;
// cout << cnt <<" "<<res<<endl;
// cout <<cnt<<endl;
//获得第一行的状态
int n = i;
while(n>0)
{
turn(1,H[(n&-n%37)],&cnt);
// cout << H[(n&-n)%37]<<" ";
n -= n&-n;
}
// cout<<endl;
// for(int i =0;i < 5;i++)cout<<matrix[1][i];
// cout <<endl;
// 模拟解法
for(int i = 1;i <= 4;i++)
{
for(int j = 0;j<5;j++)if(matrix[i][j]=='0')turn(i+1,j,&cnt);
}
//记录答案
int worth = 0;
for(int i = 0;i <5;i++)if(matrix[5][i]=='0')worth++;
if(!worth)
{
res = min(res,cnt);
// for(int i = 1; i<=5;i++)
// cout << matrix[i]<<endl;
}
// cout << cnt <<" "<<res<<endl;
// cout << endl;
//还原计数
cnt = 0;
// res = 0x3f3f3f3f;
memcpy(matrix,g,sizeof(g));
}
if(res>6)cout << "-1"<<endl;
else cout << res<<endl;
}
}