【POJ-3279】Fliptile
题目要求
Description
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 × 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”.
Input
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
Output
Lines 1…M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
Sample Input
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
Sample Output
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
解题思路
一开始我用纯dfs进行搜索，枚举每一个点，毫无疑问，直接TLE，后来考虑，既然我们不能枚举所有操作，那我们不如只枚举一行的操作，然后根据这一行的操作来推出后面每一行的操作，最后判断能不能满足题目要求，即所有的棋子均为白色。
我们怎样推出后面每一行的操作呢？我们从第二行开始，枚举每一行的点，如果这个点正上方的一个点是黑色的，那么为了满足题意，只有将该棋子翻过来，才能使上面的棋子变成白色的。因为这个翻转棋只有两面，如果翻两次的话就相当于没翻，所以我们只需要标记需不需要翻即可。
在枚举操作的时候，因为数量较小，而且每个棋子只有两种情况（翻与不翻），所以使用二进制枚举。
把以上几点考虑到，就可以顺利写出代码了hhh
AC代码
#include<iostream>
#include<string>
#include<memory.h>
using namespace std;int Map[20][20],cal[20][20],ans[20][20];
int n,m;
int dir[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};int getcolor(int x,int y)//根据原图中的颜色以及该点及周围点的反转情况，确定该点此时的颜色。
{int ans=Map[x][y];for(int i=0;i<5;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx<0||ty<0||tx>=n||ty>=m)continue;//防止越界else ans+=cal[tx][ty];}return ans%2;
}int dfs()
{for(int i=1;i<n;i++)for(int j=0;j<m;j++)if(getcolor(i-1,j)==1)//如果某点的上方当前为黑色，则只能将该点翻转使得上方的点变成白色。cal[i][j]=1;for(int i=0;i<m;i++)if(getcolor(n-1,i)==1)//如果最后一行有黑色的，则说明这种翻转方式不成立。return -1;int ans=0;for(int i=0;i<n;i++)//每有一步翻转，就记录一下for(int j=0;j<m;j++)ans+=cal[i][j];return ans;//返回总步数
}int main(void)
{while(cin>>n>>m){for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>Map[i][j];int res=(1<<30)-1;for(int i=0;i<1<<m;i++)//根据字典序从小到大的顺序二进制枚举第一行的每一种操作。{memset(cal,0,sizeof(cal));//这里每次都要初始化一下cal数组for(int j=m;j>0;j--){int num=m-j;int temp=1<<(j-1);if(i&temp)cal[0][num]=1;}int now=dfs();if(now>=0&&now<res){res=now;memcpy(ans,cal,sizeof(cal));}}if(res==(1<<30)-1)cout<<"IMPOSSIBLE"<<endl;elsefor(int i=0;i<n;i++){for(int j=0;j<m;j++)if(j==0)cout<<ans[i][j];else cout<<" "<<ans[i][j];cout<<endl;} }return 0;
}