Description
There’s an N X M board which filled with black and white chesses.
In each move, the player can flip one of these N X M chesses, meanwhile some chesses of its 8 neighbors will switch into its opposite color(from black to white and from white to black).
Here’s four change pattern of the flip operation:
1. .*.
* * ('*' denotes the position which will change its color, '.' denotes that the color will stay the same.)
.*. It means the chesses of the choosen position's up, down, left and right will switch its color.
(Don't forgot the chess which the player choose, it'll also switch its color.)
2. **.
* *
*.. It means the chesses of its upper-left, up, left, right and bottom-left will switch its color.
3. .**
* *
.*. It means the chesses of its up, upper-right, left, right and down will switch its color.
4. .**
* .
.** It means the chesses of its up, upper-right, left, down and bottom-right will switch its color.
At the beginning, the player should choose one of these four patterns to flip (the player can only use one pattern in a single game), then try to switch the board into all white.By the way, we want to find a solution with minimal number of operations, if ties, select the smaller index of pattern.
Input
There are multiple test cases (no more than 150).
The first line of each case contains two integer numbers N and M (1 <= N, M <= 15), indicating the width and the height of the board.
The following N lines containing M characters each describe the initial state of the board. ‘0’ and ‘1’ correspond to white and black, respectively.
Input ends with 0 0.
Output
For each test case output the optimal solution, the pattern should be choosen follows by the minimal number of operations.
If none of these four pattern can switch the board into all white, output “Impossible” for the test case.
Sample Input
1 1
1
3 2
11
10
11
5 5
00000
00110
01110
00100
00000
0 0
Sample Output
1 1
4 1
3 1
题目大意：
就是给定一个
能不能通过这四种方式使得给定的初始状态变为全是白色的状态，如果有的话输出最小的按动的次数并且输出是使用的哪种方式，否则输出
解题思路：
其实这就是一个翻转的问题，只不过情况多了一点而已，其实根据每种方式列出系数矩阵，然后枚举*变量就
方式就行。具体看一下 我的代码就明白了。
/**
2016 - 09 - 09 下午
Author: ITAK
Motto:
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9+5;
const int MAXN = 250;
const int MOD = 1e9+7;
const double eps = 1e-7;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///输入外挂
{
LL res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
int Scan_Int()///输入外挂
{
int res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
void Out(LL a)///输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}
int equ, var;///equ个方程 var个变量
int a[MAXN][MAXN];///增广矩阵
int x[MAXN];///解集
int x_i[MAXN];
bool free_x[MAXN];///判断是不是*变元
int free_num;///*变元的个数
int Gauss()
{
int Max_r;///当前列绝对值最大的存在的行
///col：处理当前的列
int row,col = 0;
int free_x_num;
int free_index;
free_num = 0;
for(int i=0; i<=var; i++)
{
x[i] = 0;
free_x[i] = 1;
}
for(row=0; row<equ&&col<var; row++,col++)
{
Max_r = row;
for(int i=row+1; i<equ; i++)
if(abs(a[i][col]) > abs(a[Max_r][col]))
Max_r = i;
if(a[Max_r][col] == 0)
{
free_x[col] = 1;
x_i[free_num++] = col;
row--;
continue;
}
if(Max_r != row)
for(int i=col; i<var+1; i++)
swap(a[row][i], a[Max_r][i]);
///消元
for(int i=row+1; i<equ; i++)
if(a[i][col])
for(int j=col; j<var+1; j++)
a[i][j] ^= a[row][j];
}
for(int i=row; i<equ; i++)
if(a[i][col])
return -1;///无解
///保证对角线主元非 0
for(int i=0; i<equ; i++)
{
if(!a[i][i])
{
int j;
for(j=i+1; j<var; j++)
if(a[i][j])
break;
if(j == var)
break;
for(int k=0; k<equ; k++)
swap(a[k][i], a[k][j]);
}
}
if(row < var)
return var - row;///*变元的个数
///回代，得到解集
for(int i=var-1; i>=0; i--)
{
x[i] = a[i][var];
for(int j=i+1; j<var; j++)
x[i] ^= (a[i][j] && x[j]);
}
return 0;///唯一解
}
void Debug()
{
puts("");
cout<<"+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++"<<endl;
for(int i=0; i<equ; i++)
{
for(int j=0; j<var+1; j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<"+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++"<<endl;
puts("");
}
int n, m;
int b[MAXN];
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
void Init1()///第一种方式
{
memset(a, 0, sizeof(a));
memset(x, 0, sizeof(x));
for(int i=0; i<equ; i++)
a[i][var] = b[i];
for(int i=0; i<var; i++)
{
int ta = i % m, tb = i / m;
a[i][i] = 1;
if(ta > 0)
a[i-1][i] = 1;
if(tb > 0)
a[i-m][i] = 1;
if(ta < (m-1))
a[i+1][i] = 1;
if(tb < (n-1))
a[i+m][i] = 1;
}
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
void Init2()///第二种方式
{
memset(a, 0, sizeof(a));
memset(x, 0, sizeof(x));
for(int i=0; i<equ; i++)
a[i][var] = b[i];
for(int i=0; i<var; i++)
{
int ta = i % m, tb = i / m;
a[i][i] = 1;
if(ta > 0)
a[i-1][i] = 1;
if(tb > 0)
a[i-m][i] = 1;
if(ta < (m-1))
a[i+1][i] = 1;
if(ta>0 && tb>0)
a[i-m-1][i] = 1;
if(ta>0 && tb<(n-1))
a[i+m-1][i] = 1;
}
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
void Init3()///第三种方式
{
memset(a, 0, sizeof(a));
memset(x, 0, sizeof(x));
for(int i=0; i<equ; i++)
a[i][var] = b[i];
for(int i=0; i<var; i++)
{
int ta = i % m, tb = i / m;
a[i][i] = 1;
if(ta > 0)
a[i-1][i] = 1;
if(tb > 0)
a[i-m][i] = 1;
if(ta < (m-1))
a[i+1][i] = 1;
if(tb < (n-1))
a[i+m][i] = 1;
if(ta<(m-1) && tb>0)
a[i-m+1][i] = 1;
}
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
void Init4()///第四种方式
{
memset(a, 0, sizeof(a));
memset(x, 0, sizeof(x));
for(int i=0; i<equ; i++)
a[i][var] = b[i];
for(int i=0; i<var; i++)
{
int ta = i % m, tb = i / m;
a[i][i] = 1;
if(ta > 0)
a[i-1][i] = 1;
if(tb > 0)
a[i-m][i] = 1;
if(tb < (n-1))
a[i+m][i] = 1;
if(ta<(m-1) && tb>0)
a[i-m+1][i] = 1;
if(ta<(m-1) && tb<(n-1))
a[i+m+1][i] = 1;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0)
break;
equ = var = n*m;
char ch;
int ans = INF;
for(int i=0; i<equ; i++)
{
cin>>ch;
b[i] = ch-'0';
}
Init1();
int tmp1 = Gauss(), sum1 = INF;
int all1 = 1<<tmp1;
for(int i=0; i<all1; i++)
{
int sum = 0;
for(int j=0; j<tmp1; j++)
{
if(i & (1<<j))
x[x_i[j]] = 1;
else
x[x_i[j]] = 0;
}
for(int ii=var-tmp1-1; ii>=0; ii--)
{
x[ii] = a[ii][var];
for(int j=ii+1; j<var; j++)
x[ii] ^= (a[ii][j] && x[j]);
}
for(int j=0; j<var; j++)
sum += x[j];
sum1 = min(sum1, sum);
ans = min(sum, ans);
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
Init4();
int tmp4 = Gauss();
int all4 = 1<<tmp4, sum4 = INF;///回代
for(int i=0; i<all4; i++)
{
int sum = 0;
for(int j=0; j<tmp4; j++)
{
if(i & (1<<j))
x[x_i[j]] = 1;
else
x[x_i[j]] = 0;
}
for(int ii=var-tmp4-1; ii>=0; ii--)
{
x[ii] = a[ii][var];
for(int j=ii+1; j<var; j++)
x[ii] ^= (a[ii][j] && x[j]);
}
for(int j=0; j<var; j++)
sum += x[j];
sum4 = min(sum4, sum);
ans = min(sum, ans);
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
Init2();
int tmp2 = Gauss();
int all2 = 1<<tmp2, sum2 = INF;
for(int i=0; i<all2; i++)
{
int sum = 0;
for(int j=0; j<tmp2; j++)
{
if(i & (1<<j))
x[x_i[j]] = 1;
else
x[x_i[j]] = 0;
}
for(int ii=var-tmp2-1; ii>=0; ii--)
{
x[ii] = a[ii][var];
for(int j=ii+1; j<var; j++)
x[ii] ^= (a[ii][j] && x[j]);
}
for(int j=0; j<var; j++)
sum += x[j];
sum2 = min(sum2, sum);
ans = min(sum, ans);
}
/**+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++**/
Init3();
int tmp3 = Gauss();
int all3 = 1<<tmp3, sum3 = INF;
for(int i=0; i<all3; i++)
{
int sum = 0;
for(int j=0; j<tmp3; j++)
{
if(i & (1<<j))
x[x_i[j]] = 1;
else
x[x_i[j]] = 0;
}
for(int ii=var-tmp3-1; ii>=0; ii--)
{
x[ii] = a[ii][var];
for(int j=ii+1; j<var; j++)
x[ii] ^= (a[ii][j] && x[j]);
}
for(int j=0; j<var; j++)
sum += x[j];
sum3 = min(sum3, sum);
ans = min(sum, ans);
}
if(tmp1==-1 && tmp2==-1 && tmp3==-1 && tmp4==-1)///无解
puts("Impossible");
else
{
if(sum1 == ans)///比对过程
printf("1 %d\n",ans);
else if(sum2 == ans)
printf("2 %d\n",ans);
else if(sum3 == ans)
printf("3 %d\n",ans);
else
printf("4 %d\n",ans);
}
}
return 0;
}