问题 B: [Usaco2007 Open]Fliptile 翻格子游戏
时间限制: 5 Sec 内存限制: 128 MB
题目描述
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M x N grid (1 <= M <= 15; 1 <= N <= 15) of square tiles, each of which is colored black on one side and white on the other side. As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make. Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".
输入
* Line 1: Two space-separated integers: M and N
* Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
输出
* Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
样例输入
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
样例输出
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0 OUTPUT DETAILS: After flipping at row 2 column 1, the board will look like:
0 0 0 1
1 0 1 0
1 1 1 0
1 0 0 1 After flipping at row 2 column 4, the board will look like:
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1 After flipping at row 3 column 1, the board will look like:
0 0 0 0
0 0 0 1
0 0 1 1
0 0 0 1 After flipping at row 3 column 4, the board will look like:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0 Another solution might be:
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
but this solution is lexicographically higher than the solution above.
考试第二题，由于有IMPOSSIBLE保底分，果断先做第三题，结果打完发现连IMPOSSIBLE都没时间打了，
/(ㄒoㄒ)/~~，借祥子的一句话，我招谁惹谁了！
这道题先膜一下QTY_大佬，给我讲明白了，首先这道题一定是搜索，应该不用解释吧，那么这道题最棘手的是我把它翻过来它又会把相邻的几个翻过去，这就会是一个不断绕的过程了，莫名想到了网络流“王者之剑”，于是每个人都会有一个愿望，他如果每次只翻动一个格子就好了，于是乎我们可以注意到我每翻一个格子它的上下层只改变一个，那我们能否利用这个特性去搞他呢，答案是肯定的。
由于是搜索题，我们不必去管每一次搜索是否一定对，而是去试暴力，那我们便可去枚举第一行我怎么翻，因为第一行翻法确定之后就可以采取近似贪心的策略，挨行去翻，只要上一行同一列的位置为1，我就翻它所对应的本行的位置知道最后一行，只要在最后加一个判断，去判断它最后一行是否都为0，是的话就是可行解，是的，可行解，因为题目要求字典序最小，这个我们待会再说，那我们怎么枚举第一行的翻法呢，感谢QTY_，状压就可以了，时间复杂度也是很好算的，状压是2^15，枚举就是枚举每个格子，最大才225，没毛病。
那么我们再来解释下字典序这个烦人的东西，说实在的，题目给的字典序到底是怎么来的只能自己推，由样例和注释可知，即使1的个数一样也是有区别的，那么观察可发现样例输出的第一个1位置比注释中的解靠前，因此可以大胆的猜测可以以进制的思想去搞它。
但这道题还没完，细心的人可能会发现本题中并未保证每个格子翻动次数只为1或0，也就是说每个格子在解中可能翻动了好几次，而按照上面的说法貌似只有0和1，是不是欺负数据水呢?当然不是假设有一种解为：
0 1
2 0
那么它完全等价为
0 1
0 0
以此类推，大于1只是可行解，不是最优解。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,b[][];
int a[][],an[][];
int mn=0x7fffffff,mi,ans[][];
void dfs(int x){
memset(an,,sizeof(an));
memcpy(b,a,sizeof(a));
for(int i=;i<=n;i++)
{
if((<<(i-))&x)
{
an[][i]=;
b[][i]^=;
b[][i-]^=;
b[][i+]^=;
b[][i]^=;
}
}
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
if(b[i-][j])
{
an[i][j]=;
b[i-][j]^=;
b[i][j]^=;
b[i][j-]^=;
b[i][j+]^=;
b[i+][j]^=;
}
}
}
bool yx=;
for(int i=;i<=n;i++)
{
if(b[m][i])
{
yx=;
break;
}
} if(yx)
{ int js=,be=;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
if(an[i][j])
{
js++;
if(!be)
be=(i-)*+j;
}
}
}
if(js<mn)
{
mn=js;
mi=be;
memcpy(ans,an,sizeof(an));
}
else if(js==mn&&be<mi)
{
mi=be;
memcpy(ans,an,sizeof(an));
}
}
}
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=;i<(<<n);i++)
{
dfs(i);
}
if(mn==0x7fffffff)
{
printf("IMPOSSIBLE\n");
}
else
{
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
printf("%d ",ans[i][j]);
printf("\n");
}
}
return ;
}