[数据结构与算法]PREV-144 卡片换位【第七届】【省赛】【C组】——bfs问题

你玩过华容道的游戏吗？
这是个类似的，但更简单的游戏。
看下面 3 x 2 的格子

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

输入格式

输入两行6个字符表示当前的局面

输出格式

一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）

输入样例

在提交之后，系统测试系统给我爆出了有一个测试用例不通过，我打开看了一下，发现是这个测试用例的错误。它的测试用例是没有给空格，而题目中说有一个格子是空着的。这就是那个测试用例：

*A*
*B*

而正确的应该是：

*A
*B*

输出样例

10

代码

在这道题目中，难点就是在二维数组向着不同方向转化时，怎么去记录二维数组的情况。
还有，这道题只要求A和B的位置实现互换，不考虑其他牌的情况。

#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include <queue>

using namespace std;

struct Node
{
	int x;    // 记录空格所在的行 
	int y;    //记录空格所在的列 
	int ax;   //记录A所在的行 
	int ay;   //记录A所在的列 
	int bx;   //记录B所在的行 
	int by;   //记录B所在的行 
	int step; //记录广搜的步数，依据此输出到达目标所走的步数 
	string s; //将二维数组转化为字符串，记录每一次广搜时二维数组的变化 
};
char str[2][3];   //定义二位字符数组 
int Ax,Ay,Bx,By,spaceX,spaceY;  //Ax,Ay,Bx,By记录在键入二维数组时A，B所在的行和列
								//spaceX,spaceY记录在键入二维数组时空格所在的行和列 
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };   //定义四个方向，在二维数组中，空格可以上下左右去移动 
map<string, bool> mp;   //定义一个map，记录二维数组转化的字符串，防止有重复的情况出现
                        //这道题不同于其他的广搜题目，这个只能根据空格去移动，
						//并且我们要去将二维数组的每一个变化能够去记录
						//而在每一步的广搜时，不同方向上的二维数组的变化是不同的 

void bfs()
{
	//定义一个开始结点，初始化节点 
	Node start;
	start.x = spaceX;
	start.y = spaceY;
	start.ax = Ax;
	start.ay = Ay;
	start.bx = Bx;
	start.by = By;
	start.step = 0;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<3;j++)
		{
			start.s += str[i][j];
		}
	}
	
	//定义一个队列，将开始结点放入 
	queue<Node> q;
	q.push(start);
	//标记键入的二维数组转化为的字符串为true,代表这个情况已经出现 
	mp[start.s] = true;
	
	while(!q.empty())
	{
		//取出队首元素 
		Node now = q.front();
		q.pop();
		
		int step = now.step;
		//在空格节点移动的过程中，假如与A或者B发生交换
		//那么就改变相应的ax,ay或者bx,by的改变
		//本题要求的是，最后不考虑其他的影响，
		//只考虑相较于最开始的情况，在ax,ay或者bx,by的改变后，最后A和B是否完成位置上的互换 
		if(now.bx == Ax && now.by == Ay &&
		   now.ax == Bx && now.ay == By)
		{
	   		cout<<step<<endl;
	   		return;
		}
		
		//将结点字符串转化为二维数组 
		char Str[2][3];
		int count = 0;
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				Str[i][j] = now.s[count];
				count++;
			}
		}
		
		//在空格所在的位置，沿着四个方向进行广搜 
		for(int i=0;i<4;i++)
		{
			//因为根据一个二维数组向四个方向进行广搜，得到的结果不一样
			//而这四个方向的广搜又都是基于这一个Str二维数组
			//因此在方向变化时，我们要定义一个辅助数组helpStr回到Str这个二维数组，再向下一个方向去延伸 
			char helpStr[2][3];
			for (int row = 0; row < 2; row++)
			{
				for (int col = 0; col < 3; col++)
				{
					helpStr[row][col] = Str[row][col];
				}
			}
			
			Node next;
			next.x = now.x + dir[i][0];
			next.y = now.y + dir[i][1];
			
			//判断变化后的空格的位置是否在数组范围之内 
			if(next.x>=0 && next.x<2 &&
			   next.y>=0 && next.y<3)
			{
				//如果空格即将到达的位置上是'*'，交换两者的元素
				//此时A和B的位置没有发生变化，就继承上一个结点的A和B的位置，步数加一
			   	if(helpStr[next.x][next.y] == '*')
			   	{
			   	   char tmp = helpStr[next.x][next.y];
			   	   helpStr[next.x][next.y] = helpStr[now.x][now.y];
			   	   helpStr[now.x][now.y] = tmp;
			   	   
			   	   next.ax = now.ax;
			   	   next.ay = now.ay;
			   	   next.bx = now.bx;
			   	   next.by = now.by;
			   	   next.step = now.step+1;
			   	}
			   	//如果空格即将到达的位置上是'A'，交换两者的元素
				//此时A的位置发生变化，即此时'A'要去往空格所在位置，即上一个结点的空格位置就为A新的位置 
				//而B的位置未发生变化，就继承上一个节点的B的位置，步数加一 
			   	if(helpStr[next.x][next.y] == 'A')
			   	{
			   	   char tmp = helpStr[next.x][next.y];
			   	   helpStr[next.x][next.y] = helpStr[now.x][now.y];
			   	   helpStr[now.x][now.y] = tmp;
			   	   
			   	   next.ax = now.x;
			   	   next.ay = now.y;
			   	   next.bx = now.bx;
			   	   next.by = now.by;
			   	   next.step = now.step+1;
			   	}
			    //如果空格即将到达的位置上是'B'，交换两者的元素
				//此时B的位置发生变化，即此时'B'要去往空格所在位置，即上一个结点的空格位置就为B新的位置 
				//而A的位置未发生变化，就继承上一个节点的B的位置，步数加一
			   	if(helpStr[next.x][next.y] == 'B')
			   	{
			   	   char tmp = helpStr[next.x][next.y];
			   	   helpStr[next.x][next.y] = helpStr[now.x][now.y];
			   	   helpStr[now.x][now.y] = tmp;
			   	   
			   	   next.bx = now.x;
			   	   next.by = now.y;
			   	   next.ax = now.ax;
			   	   next.ay = now.ay;
			   	   next.step = now.step+1;
			   	}
			   	
			   	//将二维数组转化为字符串 
			   	string news = "";
			   	for (int i = 0; i < 2; i++)
				{
					for (int j = 0; j < 3; j++)
					{
						news += helpStr[i][j];
					}
				}
				
				//判断这个字符串的情况是否出现过 
				if(!mp[news])
				{
					mp[news] = true;
					next.s = news;
					q.push(next);  //没有出现过，就放到map中，并标记出现了，放到队列中 
				}
			}
		}
	}
}

int main()
{
	//键入二维数组 
	for(int i=0; i<2; i++)
	{
		gets(str[i]);
	}
	
	//找寻第一次时A，B和空格所在的位置 
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(str[i][j] == 'A')
			{
				Ax = i;
				Ay = j;
			}
			if(str[i][j] == 'B')
			{
				Bx = i;
				By = j;
			}
			if(str[i][j] == ' ')
			{
				spaceX = i;
				spaceY = j;
			}
		}
	}
	
	bfs();
	
	return 0;
}