POJ 3279 搜索

Time limit 2000 ms
Memory limit 65536 kB
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
题目描述
题目的意思是，给你一个地图，上面有白色的瓦块（用0表示）和黑色的瓦块（用1表示），现在可以对瓦块进行反转，我想了下，这不是黑白棋吗？不过这个和黑白棋还是不一样的，在这里，若对其中一块瓦块进行反转，那么它的四周的瓦块也会进行反转，题目需要我们用到最小反转次数去让整个地图的瓦片变成白色的，最终输出的是对应位置的瓦块反转的次数，而且存在多个最优解的时候，要求让由输出的图组成的字符串按逆字典序小的图输出。

试想一下，如果反转的时候会让它的四周的瓦块同时发生反转，那么对于第一行，它不能通过只对这一行进行反转得到全白色瓦块，它只能通过第二行和第一行的反转进行结合，来让第一行的黑色瓦块变成白色瓦块；而对于最后一行的黑色瓦块，也只能通过倒数第二行和本行的结合让其中的黑色瓦块全部变成白色瓦块。

所以我们的方法是，先将第一排的所有可能的反转情况全部逆字典序地进行枚举，这样我们就可以在同为最少步骤的时候，不需要再进行判断了，因为在同一反转次数下，逆字典序最小的先得出了。然后我们对第二行行进行枚举，若在某一列的上方，比如(2,4)和(1,4)，如果上方有黑色的瓦块，那么只有通过这个位置的瓦块（此处为（2，4））进行反转，才可以让上方的瓦块变成白色。那么倒数第二行就很关键了，因为这一行造成的反转不仅要让倒数第三行的黑色瓦块变成白色瓦块，同时也要让最后一行的黑色瓦块变成白色瓦块，所以当我们利用最后一行，让倒数第二行的黑色瓦块全部变成了白色瓦块之后，如果此时最后一行的瓦块不全是白色的，说明这一操作的不成功。

如果通过上面的操作让整个地图变成了白色的话，就说明这一反转的方法可以成功。

为了能够输出结果，我们需要对进行反转的瓦块进行标记，由于同一块瓦片反转2次和没反转一样，所以我们规定每一块瓦块最多主动反转一次（作为中心块进行的反转），这一标记同时也代表了对地图上每一块瓦块的操作次数，可以作为答案输出，不过在此之前，我们需要统计一共进行了多少次的主动反转，然后找出最少的那一次输出，具体实现请看代码。

#include"iostream"
#include"cstdio"
#include"stdlib.h"
#include"cmath"
#include"cstring"
#include"cstdlib"
#include"vector"
#include"stack"
#include"queue"
#include"set"
#include"map"
#include"algorithm"
#include <utility>
#include <iomanip>
#include <time.h>
#include<list>
const double PI=acos(-1.0);
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define inf 0x3f3f3f3f
#define pr pair<int,int>

typedef pair<char,int> PAIR;
struct CmpByValue
{
   
    bool operator()(const PAIR& lhs, const PAIR& rhs)
    {
   
        return lhs.second > rhs.second;
    }
};
//priority_queue<int,vector<int>,greater<int>> pp;
const int mod = 123456789 ;
const int M = 17 ;
const int limt = 1<<20;
const int INF = 1e9;
typedef long long ll;

int mp[M][M];                               //实际地图
int choose[17][17];						//表示反转的情况

int m,n;

int to[5][2]= {
    {
   0,0},{
   1,0},{
   -1,0},{
   0,1},{
   0,-1} }; // 表示要反转的，包括自己
//判断坐标为(x,y)的点的颜色，用0和1表示
int col(int x,int y)
{
   
	int s = mp[x][y];				//先记录初始颜色
	for(int i = 0 ;i < 5 ; i++)
	{
   
		int tx = x + to[i][0];
		int ty = y + to[i][1];
		s += choose[tx][ty];		        //choose[tx][ty]代表(tx,ty)的瓦块是否被反转过，由于颜色只用0,1表示，那么只需要加一个 1 就代表反转，加0表示不变
						        //而对于这个瓦块是否被反转，主要取决于他邻近的4个瓦块以及自身是否进行了反转
	}
	return s % 2;					//由于每加一代表一次颜色的反转，但是我们需要的只是0,1，所以在这里我们将之转化会用0，1表示
}

int solve()
{
   
    int sum = 0;					//记录反转的总次数
    for(int i = 2 ; i <=m ; i++)			//从第二行开始枚举
    {
   
        for(int j = 1 ; j <= n ; j ++)
        {
   
            if(col(i-1,j) == 1)		//这一块的上一块是黑色的，那么就对当前这块进行反转，来让上面的那一块变成白色
            {
   
                choose[i][j] = 1;	//对这一块进行反转，从而让这一块上面的瓦块变成白色
                sum++;			//代表反转次数加一
            }
        }
    }

    for(int i = 1 ; i <= n ; i ++)
    {
   
        if(col(m,i))				//若最后一行有黑色的瓦块，说明这种方法是失败的
        {
   
            return -1;			//失败返回-1
        }
        sum += choose[1][i];			//顺便将第一行所用的步数加上
    }

    return  sum;					//成功返回反转的次数

}
int main()
{
   
    while(~scanf("%d%d",&m,&n))
    {
   
        for(int i = 1 ; i <=  m ; i ++)
        {
   
            for(int j = 1 ; j <= n ; j ++)
            {
   
                scanf("%d", *(mp + i) + j);			//节省时间，使用指针
            }
        }
        int Min = -1;									//-1代表不能反转成功，将Min设为-1，是因为我们无法确定最大值
        int goal[17][17];								//存储最终方案
        for(int i = 0 ; i < (1<<n) ; i++)				//枚举第一行的2^n种反转方式
        {
   
            memset(choose, 0, sizeof(choose));			//表示对应的瓦块是否进行反转， 0 表示不反转，1，表示反转

            for (int j = 1; j  <= n; j++)				//将i对应的值转化为二进制，比如i 为3 就是 0011 ，一共n位,不过我们需要进行逆转这个，由于是按逆字典序排序，
                //所以我们只需要考虑第一行，因为第一行的情况是独一无二的，所以第一行在枚举的时候自成逆字典序的话，那么就不需要多判断了


                choose[1][j] = (i >> (j - 1)) & 1;		//记录第一行的不同的情况,

            int temp = solve();							//返回反转次数，但是由于调用了这一个函数，我们已经将反转的具体操作储存在choose中
            if(temp >= 0 && (temp < Min || Min < 0) )	        //通过异或判断可以有效地利用Min = -1 这个条件
            {
   
                Min = temp;
                memcpy(goal, choose,sizeof(choose));	        //将数据存在goal中
            }
        }
        if(Min == -1)
        {
   
            printf("IMPOSSIBLE\n");
        }
        else
        {
   
            for(int i = 1 ; i <= m ; i ++)
            {
   
                printf("%d", goal[i][1]);
                for(int j = 2; j <= n ; j ++)
                {
   
                    printf(" %d", goal[i][j]);
                }
                cout << endl;
            }
        }

    }
    return 0;
}