问题描述
你玩过华容道的游戏吗?这是个类似的,但更简单的游戏。看下面 2 x 3 的格子
+---+---+---+
| A | * | * |
+---+---+---+
| B | | * |
+---+---+---+
1
2
3
4
5
在其中放 5 张牌,其中 A 代表关羽,B 代表张飞,* 代表士兵,还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。
输入格式
输入两行 6 个字符表示当前的局面输出格式
一个整数,表示最少多少步,才能把 AB 换位(其它牌位置随意)样例输入1
* A
**B
1
2
样例输出1
17样例输入2
A B
***
1
2
样例输出2
解题思路:我是想把二维变成一维来算的,如图中的两个字符串,我把他变成* AB**来看,通过查找空格进行左移右移,具体可以看代码。可是他有一个测试点出现运行错误,很奇怪,也不像是类型超出最大值,或者数组越界,难道是队列满了?求大佬帮忙看下
不过又去看了一下,好像是它样例的问题
#include<bits/stdc++.h>
using namespace std;
map<string,long long>vis;
int x,y;
long long bfs(string s){
queue<string>q;
q.push(s);
vis[s]=0;
while(!q.empty()){
string now=q.front();
q.pop();
int pos=now.find(' ');
string temp=now;
int len=now.length();
if(x==now.find('A')&&y==now.find('B')){
return vis[now];
}
swap(now[pos],now[(pos+1)%len]);//格子往右移
if(vis[now]==0){
vis[now]=vis[temp]+1;
q.push(now);
}
swap(now[pos],now[(pos+1)%len]);
swap(now[pos],now[(pos+len-1)%len]);//格子往左移
if(vis[now]==0){
vis[now]=vis[temp]+1;
q.push(now);
}
swap(now[pos],now[(pos+len-1)%len]);
if(pos==1||pos==4){//在格子中间,还能往上下走
swap(now[pos],now[(pos+3)%len]);
if(vis[now]==0){
vis[now]=vis[temp]+1;
q.push(now);
}
// swap(now[pos],now[(pos+3)%len]);
}
}
return -1;
}
int main(){
string s1,s2;
getline(cin,s1);
getline(cin,s2);
reverse(s2.begin(),s2.end());
s1+=s2;
x=s1.find('B');
y=s1.find('A');
cout<<bfs(s1)<<endl;
return 0;
}