首页 > 代码库 > POJ1753(Flip Game)

POJ1753(Flip Game)

2024-07-04 18:43:54   230人阅读

题目大意：给你一个4*4的矩阵，矩阵里面储存着棋子，棋子有黑色，和白色，你可以任意改变位置（i，j）的棋子，但是规则是这个位置的上下左右的棋子颜色都必须改变。求最少需要改变几颗棋子，使得棋盘的棋子都为白的或都为黑色。

解题思路: 枚举+DFS。

因为棋盘就16位所以，最多改变16个棋子。枚举每一种至少改变的棋子个数。（可以是1.2.3....16）。假设枚举到至少需改变4个棋子才能达到全为黑或白，这时就需要深搜所有改变4颗棋子，棋盘的状态，如达到全为黑或白，这时就完成了至少需要的步数。

 

代码：

#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
int a[4][4];
int f;
int judge()
{
    int cnt=0;
    int i,j;
    for(i=0; i<4; i++)
        for(j=0; j<4; j++)
        {
            if (a[i][j]==1)
                cnt++;
        }
    if (cnt==0||cnt==16)
        return 1;
    return 0;
}
void change(int i,int j)
{
    a[i][j]^=1;
    if (i-1>=0)
        a[i-1][j]^=1;
    if (i+1<4)
        a[i+1][j]^=1;
    if (j-1>=0)
        a[i][j-1]^=1;
    if (j+1<4)
        a[i][j+1]^=1;
}
void dfs(int y,int cnt,int sum)
{
    int i,j;
    if (cnt==sum)
    {
        f=judge();
        return ;
    }
    if(f)   return;
    for(j=y+1; j<16; j++)
    {
        change(j/4,j%4);
        dfs(j,cnt+1,sum);
        if (f)
            return ;
        change(j/4,j%4);
    }
}
int main()
{
    int i,j;
    char c;
    int cnt=0;
    for(i=0; i<4; i++)
    {
        for(j=0; j<4; j++)
        {
            scanf("%c",&c);
            if (c==‘b‘)
            {
                a[i][j]=0;
                cnt++;
            }
            else
                a[i][j]=1;
        }
        getchar();
    }
    int sum=0;
    int ce=0;
    f=0;
    if (cnt==0||cnt==16)
    {
        printf("0\n");
        return 0;
    }
    for(i=0; i<4; i++)
        for(j=0; j<4; j++)
        {
            dfs(-1,0,++sum);
            if (f)
            {
                printf("%d\n",sum);
                return 0;
            }
        }
    printf("Impossible\n");
    return 0;
}

 


联系
我们