poj 3279 Fliptile (搜索..暴力?)

Posted by 111qqz on Thursday, July 23, 2015

TOC

http://poj.org/problem?id=3279

反转类问题.

有N*M个方格,每个上面有数字0或者1

操作一个方格,这个方格即其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0)

问至少需要多少次操作,所有的状态都为0

如果有多组,输出字典序小的那一组.

跟开关灯的那题相似.

因为每个开关灯的动作还影响其他相邻灯的状态.所以对于这种题,一般思路是,先定住一部分,再由已知定住的这部分去确定其他部分.

对于这道题而言

首先我们可以很容易发现,操作数为偶数和为0是等价的.

操作数为1和为奇数是等价的.

对于这道题而言,我们可以首先枚举第一行的状态,一共有 2<

然后如果 a[i-1][j]为1,因为i-1行的状态已经确定,无法改变,所以能影响到a[i-1][j]的只有a[i][j]

那么a[i][j]一定要操作一次

最后判断最后一行是否都为0,如果为0,表示这种情况是合法的

然后找到操作数最小的一组.

字典序的话,只要是枚举的时候按照数的大小顺序就可以保证.

学会了用memcpy函数.

    
    #include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    #include<stack>
    #define y0 abc111qqz
    #define y1 hust111qqz
    #define yn hez111qqz
    #define j1 cute111qqz
    #define tm crazy111qqz
    #define lr dying111qqz
    using namespace std;
    #define REP(i, n) for (int i=0;i<int(n);++i)  
    typedef long long LL;
    typedef unsigned long long ULL;
    const int N=20;
    int a[N][N],ans[N][N],op[N][N];
    int m,n;
    int dirx[10]={0,0,0,-1,1};
    int diry[10]={0,1,-1,0,0};
    int rec[N][N];
    void solve(int x,int y)
    {
        for ( int i = 0 ; i < 5 ; i++ )
        {
    	  int newx = x + dirx[i];
    	  int newy = y + diry[i];
    	  if (newx>=1&&newx<=m&&newy>=1&&newy<=n)
    	  {
    		a[newx][newy]=a[newx][newy]^1;
    	  }
        }
    }
    bool on (int x,int y)
    {
        int res = a[x][y];
        for ( int i = 0 ; i < 5 ; i++ )
        {
    	  int newx = x + dirx[i];
    	  int newy = y + diry[i];
    	  if (newx>=1&&newx<=m&&newy>=1&&newy<=n)
    	  {
    		res = res+op[newx][newy];
    	  }
    
        }
        return res&1;
    }
    int main()
    {
        cin>>m>>n;
        int mi = 9999999;
        memset(rec,0,sizeof(rec));
        for ( int i = 1 ; i <= m ; i++ )
        {
    	  for (int j = 1 ; j <= n ; j++)
    	  {
    		cin>>a[i][j];
    	  }
        }
        bool flag = false;
        for ( int i = 0  ; i < (1<<n); i++ )   //枚举第一行的好改变情况
        {
            int tmp=i;
    	  int num=0;
    	  memset(op,0,sizeof(op));
            memset(ans,0,sizeof(ans));
    	  int k = n;
    	  while (tmp)
    	  {
    		op[1][k]=tmp%2;
    		if (op[1][k]==1) num++;
    		tmp = tmp / 2;
    		k--;
    	  }
    //	  cout<<"********************"<<endl;
    //	  for ( int i = 1 ; i <= n ; i++)
    //	  {
    //		cout<<op[1][i]<<" ";
    //	  }
    //	  cout<<endl;
    //	  cout<<"*************************"<<endl;
    
    
    	  for ( int j = 2 ; j <= m ; j++ )
    	  {
    		for ( int k = 1 ; k <= n ; k++ )
    		{
    		    if (on(j-1,k))
    		    {
    			  op[j][k]=1;
    			  num++;
    		    }
    		}
    	  }
    	  bool ok = true;
    	  for ( int j = 1 ; j <= n ; j++ )
    	  {
    		if (on(m,j))
    		{
    		    ok=false;
    		    break;
    		}
    	  }
    	  if (ok)
    	  {
    		flag = true;
    		if (num<mi)
    		{
    		    mi = num;
    		    memcpy(rec,op,sizeof(op));
    		 //   for ( int j = 1 ; j <= m ; j ++ )
    		//    {
    		//	  for ( int k = 1 ;  k <= n ; k++ )
    		//	  {
    	//			rec[j][k]=ans[j][k];
    	//		  }
    //		    }
    		}
    	  }
        }
        if (flag)
        {
    	  for ( int i = 1 ; i <= m ; i++ )
    	  {
    		cout<<rec[i][1];
    		for ( int j = 2 ; j <= n ; j++ )
    		{
    		    cout<<" "<<rec[i][j];
    		}
    		cout<<endl;
    	  }
        }
        else
        {
    	  printf("IMPOSSIBLE\n");
        }
    
    	return 0;
    }