Press "Enter" to skip to content

POJ1753 Flip Game

深搜枚举

POJ 1753

题目

Flip game is played on a rectangular 4×4 field with two-sided
pieces placed on each of its 16 squares. One side of each
piece is white and the other one is black and each piece is
lying either it’s black or white side up. Each round you flip
3 to 5 pieces, thus changing the color of their upper side
from black to white and vice versa. The pieces to be flipped
are chosen every round according to the following rules:
1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).


输入

bwwb
bbwb
bwwb
bwww

输出

4

题意

给出一张4×4的图,每次可以选择一个位置进行翻转,每次翻转会把(i,j)及其上下左右四个位置同时进行翻转。求出把这个图全翻转成同一面的最小步骤,无解输出”Impossible”。

bwbw
wwww
bbwb
bwwb

操作第一个字母后为

wbbw
bwww
bbwb
bwwb

思路

图的大小为4×4,每个位置翻转奇数次相当于翻转一次,翻转偶数次相当于没有翻转,因此只需记录是否需要进行翻转。共有2^16种可能,直接dfs即可。

代码

#include<iostream>
using namespace std;

bool mapx[5][5];
bool flag;

bool judge()
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(mapx[i][j]!=mapx[0][0])
                return false;
    return true;
}
void flip(int i,int j)
{
    mapx[i][j]=!mapx[i][j];
    if(i+1<4)
        mapx[i+1][j]=!mapx[i+1][j];
    if(j+1<4)
        mapx[i][j+1]=!mapx[i][j+1];
    if(i-1>=0)
        mapx[i-1][j]=!mapx[i-1][j];
    if(j-1>=0)
        mapx[i][j-1]=!mapx[i][j-1];
}

void dfs(int i,int j,int depth,int step)
{
    if(depth==step) 
    {
        flag=judge();
        return;
    }
    if(flag || i==4)
        return;
    flip(i,j);
    if(j<3)
        dfs(i,j+1,depth+1,step);
    else
        dfs(i+1,0,depth+1,step);
    flip(i,j);
    if(j<3)
        dfs(i,j+1,depth,step);
    else
        dfs(i+1,0,depth,step);
    return;
}

int main()
{
    for(int i=0;i<4;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<4;j++)
        {
            if(s[j]=='b')
                mapx[i][j]=0;
            else
                mapx[i][j]=1;
        }
    }
    int w;
    for(w=0;w<=16;w++)
    {
        dfs(0,0,0,w);
        if(flag)
            break;
    }
    if(flag)
        cout<<w<<endl;
    else
        cout<<"Impossible"<<endl;
    return 0;
}

Be First to Comment

发表评论

电子邮件地址不会被公开。