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
推荐阅读
-
三星Galaxy Z Flip变身翻盖手机 摩托罗拉:笑而不语
-
蔡依林上手三星翻盖折叠屏手机Galaxy Z Flip:真铁粉
-
三星Galaxy Z Flip折叠玻璃真的厉害吗?
-
本月发货 三星Galaxy Z Flip折叠屏宣布国行先行者计划
-
华硕Chromebook Flip C100笔记本开售 售价250美元起
-
三星Galaxy Z Flip视频上手 :上下折叠真机全面泄露
-
MAC升级OS X 10.8后Game Center无法连接怎么修复?
-
三星Galaxy Z Flip保护壳是什么样子?围观欣赏
-
PHP array_flip() 删除重复数组元素专用函数
-
小米9新增Game Tubro游戏模式:骁龙855智能无卡顿