网站开发的安全性原则,郑州网站建设行情,庆阳官网贴吧,上海网站建设渠道题目描述 你玩过华容道的游戏吗#xff1f;这是个类似的#xff0c;但更简单的游戏。看下面 3 x 2 的格子
在其中放5张牌#xff0c;其中A代表关羽#xff0c;B代表张飞#xff0c;* 代表士兵。还有一个格子是空着的。 你可以把一张牌移动到相邻的空格中去(对角不算相邻…题目描述 你玩过华容道的游戏吗这是个类似的但更简单的游戏。看下面 3 x 2 的格子
在其中放5张牌其中A代表关羽B代表张飞* 代表士兵。还有一个格子是空着的。 你可以把一张牌移动到相邻的空格中去(对角不算相邻)。 游戏的目标是关羽和张飞交换位置其它的牌随便在哪里都可以。 输入 输入存在多组测试数据对于每组测试数据 输入两行6个字符表示当前的局面 输出 对于每组测试数据输出一个整数表示答案 解题思路
fir//表示最开始的情况
tem//上一步的情况
now//表示现在的情况为了避免避免出现重复的形况而无限循环无结果的情况我们可以用一个vis数组用来标记只要我们标记A,B空格的位置标示这个情况已经出现过以后就不会出现同样的情况了。 在这里由于要读入空格我们用gets来读入。 以下两种读入的方法遇到空格都会停下来。
char s[5][5];
scanf(%s,s[0]);
cins[0];如果现在的情况的空格位置与上一步的A的位置相同那么现在的情况的A位置应该是上一步的空格位置同理如果现在的情况的空格位置与上一步的B的位置相同那么现在的情况的B位置应该是上一步的空格位置代码如下 if (xxtem.ax yytem.ay){now.ax tem.kx;now.ay tem.ky;}else{now.ax tem.ax;now.ay tem.ay;}if (xxtem.bx yytem.by){now.bx tem.kx;now.by tem.ky;}else{now.bx tem.bx;now.by tem.by;}终止条件便是现在的A的坐标与最开始的B坐标相同现在的B坐标与最开始的A坐标相同
if (now.ax fir.bx now.ayfir.by now.bxfir.ax now.byfir.ay)在这道题中之所以要到最后面才开始检查有没有这种情况出现是因为要走过才能得到这种情况是什么样子的。不然你vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky]里面的now.ax,now.ay的值怎么得到。
代码如下
#include iostream
#include cstring
#include queue
using namespace std;
const int N 8;
char s[N][N];
bool vis[N][N][N][N][N][N];
int dx[] {0,0,1,-1},dy[] {1,-1,0,0};
struct node
{int ax,ay,bx,by,kx,ky,step;
};int bfs(node fir)
{memset(vis,0,sizeof(vis));queuenodeq;fir.step 0;vis[fir.ax][fir.ay][fir.bx][fir.by][fir.kx][fir.ky] true;q.push(fir);while(q.size()){node tem q.front();q.pop();for (int i 0;i4;i){int xx tem.kxdx[i],yy tem.kydy[i];if (xx 0 xx 2 yy 0 yy 3){node now;now.kx xx;now.ky yy;now.step tem.step1;if (xxtem.ax yytem.ay){now.ax tem.kx;now.ay tem.ky;}else{now.ax tem.ax;now.ay tem.ay;}if (xxtem.bx yytem.by){now.bx tem.kx;now.by tem.ky;}else{now.bx tem.bx;now.by tem.by;}if (now.ax fir.bx now.ayfir.by now.bxfir.ax now.byfir.ay){return now.step;}if (vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky]0){vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky] true;q.push(now);}}}}return -1;
}int main()
{while(gets(s[0])!NULL){gets(s[1]);node fir;for (int i 0;i2;i)for (int j 0;j3;j){if (s[i][j]A){fir.ax i;fir.ay j;}else if (s[i][j]B){fir.bx i;fir.by j;}else if (s[i][j] ){fir.kx i;fir.ky j;}}coutbfs(fir)endl;}return 0;
}
