Description
Flip game is played on a rectangular 4x4 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:
- Choose any one of the 16 pieces.
- 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).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible"
(without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
给十六个格子标上序号
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
便可以采用二进制记录不同的状态
01 0 0 0 1 1 0 0 0 1 1 0 1
1 1
1514 13 12 1110 9 8 7 65 4 32
1 0
此时便记录下了
14 10 9 5 4 2 1 0
最后采用十进制保存此时的状态 1表示‘b’,0表示‘w’,再做相应的翻转,既0 -> 1, 1 -> 0
#include<iostream>
#include<cstring>
using namespace std;
char ma[5][5];//用于输入
int states[65535]={0};//(核心部分)记录状态因为最大为2^16-1=65535所以数组大小为65535
int step[65535]={0};//记录步数
int rear=0,front=0;//记录头与尾
bool vis[65535];//用于记录是否搜过
//输入,并记录初始状态,放入队列首位置
void shuru()
{
int i,state=0;
for(i=0;i<4;i++){
cin>>ma[i];
int j;
for(j=0;j<4;j++)
if(ma[i][j]=='b')
state|=1<<(i*4+j);
}
states[rear++]=state;//记录初始状态放入队列首
vis[state]=true;//记录已走过
}
//反转一个,并产生影响
int fanzhuan(int stat,int i)
{
int state=0;
state|=1<<i;
if(i%4!=0)state|=1<<(i-1);
if((i+1)%4!=0)state|=1<<(i+1);
if(i-4>=0)state|=1<<(i-4);
if(i+4<16)state|=1<<(i+4);
return (state^stat);
}
//BFS宽度遍历,搜索每种状态,不断放入队列中,找到后立即返回真(true)
bool bfs()
{
while(front<rear)
{
int state=states[front++];//取出队列头,记录此时状态
if(0==state||65535==state)//一旦找到,立即返回
{
cout<<step[state]<<"\n";
return true;
}
int i;
for(i=0;i<16;i++)//遍历每种状态
{
int st;
st=fanzhuan(state,i);
if(!vis[st])//防止重复遍历
{
states[rear++]=st;//不可以的加到队列尾部
vis[st]=true;
step[st]=step[states[front-1]]+1;//步数加1
}
}
}
return false;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
shuru();
if(!bfs())cout<<"Impossible\n";
return 0;
}
分享到:
相关推荐
dfs-bfs-master 网上找到的 dfs和bfs演示
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
2018-春季-人工智能-No03-Topic 04-确定性推理-BFS-DFS实验Python代码1
matlab开发-bfsk使用系统生成器设计。使用SysGen 10.1的BFSK收发器
作业共享MATLAB蒙特卡罗仿真估计BFSK系统的BER-bfsk_ber.rar 在二进制频移键控(BFSK)下,用蒙特卡罗仿真方法估计系统的BER 这是我用Matlab做的第一个通信系统仿真,内含注释供参考
Matlab编写的二进制调制代码OOK2ASK2FSKBPSKDPSK-BFSK.rar
降群法解魔方 哈哈师大 使用双向BFS搜素
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
graph traversal using bfs and dfs strategy
人工智能大作业:c++代码bfs解决8数码问题
网友DSA-BFS-DFS 广度优先搜索(BFS)和广度优先遍历 广度优先搜索 (BFS)是一种探索树或图的方法。 在 BFS 中,您首先探索一步之外的所有节点,然后探索两步之外的所有节点,依此类推。 广度优先搜索就像在池塘中央...
关于这是用于评估MS-BFS算法的实验框架(在VLDB 2015论文)及其相关...天真(教科书BFS),无队列(基于位字段的教科书BFS),scbfs(方向优化的BFS),parabfs(并行BFS) bWidth :每个顶点用于MS-BFS的寄存器数,例
对bfs(广度优先遍历)和dfs(深度优先遍历)的详细解析,帮助人们理解广搜和深搜
更好的理解和学会运用深sou去做一些题目
简单的图的深度搜索和广度搜索,适合初学者交流
matlab广度优先算法代码搜索算法-BFS-DFS-A-star 搜索是AI中解决问题的通用技术。 这个项目将使您开始使用这些不同的算法: 蛮力搜索策略 广度优先搜索:它从根节点开始,先探索相邻节点,然后再向下一级邻居移动。 ...
#资源达人分享计划#
py代码-bfs一般写法