欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Flip Game

程序员文章站 2022-07-10 16:12:18
Flip Game题目链接思路:这是一道典型的DFS题目,通过DFS枚举每一种情况,每个棋子都只有两种情况(非黑即白),所以共有2^n种情况,然后判断每种情况是否可以成立,并同时比较所需步骤大小。#include#include#include#includeusing namespace std;int a[4][4];int Min=0x7fffffff;in...

Flip Game

题目链接
思路:
这是一道典型的DFS题目,通过DFS枚举每一种情况,每个棋子都只有两种情况(非黑即白),所以共有2^n种情况,然后判断每种情况是否可以成立,并同时比较所需步骤大小。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[4][4];
int Min=0x7fffffff;
int check()//检查棋子是否同色
{
    int i,j;
    for(i=0; i<4; ++i)
        for(j=0; j<4; ++j)
            if(a[i][j]!=a[0][0])
                return -1;
    return 1;
}
void change(int i,int j)
{
    a[i][j]=!a[i][j];
    if(i-1>=0)
    {
        a[i-1][j]=!a[i-1][j];
    }
    if(j-1>=0)
    {
        a[i][j-1]=!a[i][j-1];
    }
    if(i+1<4)
    {
        a[i+1][j]=!a[i+1][j];
    }
    if(j+1<4)
    {
        a[i][j+1]=!a[i][j+1];
    }
}
void dfs(int d,int k)
{
    int x,y;
    if(d==16)
    {
        if(check()==1)
            if(k<Min)
                Min=k;
        return;
    }
    else
    {
        x=d/4;//行
        y=d%4;//列
        dfs(d+1,k);//没有翻的时候进行一次dfs 
        change(x,y); //翻过去
        dfs(d+1,k+1);//翻过去以后进行一次dfs 
        change(x,y);  //别忘了翻回去,这个是返回原来的状态
    }
}
int main()
{
    char t;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            cin>>t;
            if(t=='b') a[i][j]=0;
            else a[i][j]=1;
        }
    }
    dfs(0,0);
    if(Min==0x7fffffff)
        cout<<"Impossible"<<endl;
    else
        cout<<Min<<endl;
 
return 0;
}

本文地址:https://blog.csdn.net/pokerfacecyf/article/details/108585704