[蓝桥杯2016初赛]卡片换位 BFS

题目描述

你玩过华容道的游戏吗?这是个类似的,但更简单的游戏。看下面 3 x 2 的格子
    +---+---+---+
| A | * | * |
+---+---+---+
| B | | * |
+---+---+---+

在其中放5张牌,其中A代表关羽,B代表张飞,* 代表士兵。还有一个格子是空着的。
你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。

输入

输入存在多组测试数据,对于每组测试数据:
输入两行6个字符表示当前的局面

输出

对于每组测试数据输出一个整数表示答案

样例输入
Copy

* A
**B
A B
***

样例输出 Copy

17
12

题解:

1、因为棋盘只有两行,可以把他处理成一行处理(BFS的时候方便标记这个棋盘状态),注意隔离边界(用#将第一行和第二行隔离)网址:yii666.com<

2、用set集合记录走过的每一个状态,标记走过的棋盘状态文章来源地址https://www.yii666.com/article/754238.html文章地址https://www.yii666.com/article/754238.html

3、从空格位置开始搜索,目标状态是棋盘中A、B位置互换网址:yii666.com文章来源地址:https://www.yii666.com/article/754238.html

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
int dir[]={-,,,-};//左右下上
struct node
{
int x;
string s;//保存不同的图,同时用set去标记
int cnt;
}A,B,K;
void bfs()
{
queue<node>p;
p.push(K);
set<string>se;
se.insert(K.s);
while(!p.empty())
{
node now=p.front();
p.pop();
for(int i=;i<;i++)
{
string ss=now.s;
int tx=now.x+dir[i];
if((tx>=&&tx<)||(tx>&&tx<))
{
char h=ss[now.x];
ss[now.x]=ss[tx];
ss[tx]=h;
node temp;
temp.x=tx;
temp.s=ss;
temp.cnt=now.cnt+;
if(ss[B.x]=='A'&&ss[A.x]=='B')
{
cout<<temp.cnt<<endl;
//cout<<temp.s<<endl;
return ;
}
if(se.count(ss)==)//避免往回走,标记棋盘状态
{
se.insert(ss);
p.push(temp);
}
}
}
}
}
int main()
{
string str,s1,s2;
while(getline(cin,s1))
{
getline(cin,s2);
str=s1+"#"+s2;//把二行的图转化为一行,用#分割第一行和第二行
for(int i=;i<;i++)
{
if(str[i]=='A')
A.x=i;
if(str[i]=='B')
B.x=i;
if(str[i]==' ')
K.x=i;
}
K.cnt=;
K.s=str;
bfs();
} return ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png