自动搬运

查看原文

来自洛谷，原作者为

	Andorxor **

搬运于2025-08-24 21:22:38，当前版本为作者最后更新于2018-12-29 01:03:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题的关键点：

1.状态转换：由于只有01，并且二进制对应的十进制的值是唯一的，因此可以考虑将数组使用对应的十进制来进行保存，如此一来，判重也很容易实现。（因为最大的数是二进制16个1，也就是2^16-1，不会超空间）

2.搜索策略：任何一种状态都需要从16个位置作为起点开始进行扩展，扩展后合法的子状态全部加入队列中，再从队列中取出队首值进行扩展，当然同样需要把这个队首值从16个位置均考虑作为起点开始扩展，获取到的所有合法的子状态......

3.记录结果：由于判重的原因，每一个数的父节点必然是唯一的，因此可从终点（目标状态）出发，往前找其父节点的值并保存，记录当前的节点坐标和父节点的坐标，输出的时候就可以从终点不断往前面推出路径。

4.处理结果：通过（3）处理得到的结果是从终点出发的，当然可以通过简单的代码操作实现输出正解。

细节较多，需要细致写代码（要敢于动手），代码注释中有关键步骤的解释，可参考代码理解以上思路。

#include<bits/stdc++.h>
using namespace std;
char c;
int csz,mbz,cnt,a[5][5],b[5][5],vis[65540],father[65540],res[100000][4];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct Ans{
	int nx,ny,ox,oy,father;
}ans[100000];
queue<int>q;

//初始化输入起点和目标点
void init(){
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>c;
   			a[i][j]=c-'0';
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>c;
   			b[i][j]=c-'0';
		}
	}
}
//获取4*4数组二进制得到十进制数
int getDeci(int a[5][5]){
	int comb=0,cnt=0;
	for(int i=4;i>=1;i--){
		for(int j=4;j>=1;j--){
			comb+=a[i][j]*pow(2,cnt);
			cnt++;
		}
	}
	return comb;
}
//根据x修改a数组的值
void updateArr(int x,int a[5][5]){
	while(x){
		for(int i=4;i>=1;i--){
			for(int j=4;j>=1;j--){
				a[i][j]=x%2;
				x/=2;
			}
		}
	}
}
//判断是否越界且父子值要不同
bool legal(int ox,int oy,int nx,int ny){
	if(nx>=1&&nx<=4&&ny>=1&&ny<=4&&a[ox][oy]!=a[nx][ny]) 
		return true;
	else    return false;
}
void bfs(){
	q.push(csz);//从初始值开始扩展
	vis[csz]=1;
	while(!q.empty()){
		int exted=q.front();  //exted用来存储每次被扩展的数
		updateArr(exted,a);  //将a数组修改为当前被扩展的数对应的二进制
		q.pop();
		for(int i=1;i<=4;i++){  //每一种状态的数都要分别以它的十六个点为起点来进行扩展
			for(int j=1;j<=4;j++){
				int ox=i,oy=j;
				for(int k=0;k<4;k++){
					int nx=ox+dx[k],ny=oy+dy[k];
					 //标记是否有执行swap，以决定是否需要再次执行swap还原a数组状态
					int flag=0;   
					if(legal(ox,oy,nx,ny)){
						flag=1;
						int fdeci=getDeci(a);   //当前被扩展的值（当前被扩展出来的节点的父节点的值）
						swap(a[ox][oy],a[nx][ny]);
						int deci=getDeci(a);    //swap后的a数组对应的十进制值
						if(!vis[deci]){
							vis[deci]=1;
							ans[deci].father=fdeci; //存储路径
							ans[deci].nx=nx,ans[deci].ny=ny;
							ans[deci].ox=ox,ans[deci].oy=oy;
							father[deci]=fdeci;
							q.push(deci);
						}
						if(deci==mbz)   //扩展得到了目标节点
							return;
					}
					if(flag)            //需要还原a数组状态
						swap(a[ox][oy],a[nx][ny]);
				}
			}
		}
	}
}
int main(){
	init();
	csz=getDeci(a),mbz=getDeci(b);//csz：初始值，mbz：目标值
	bfs();
	father[csz]=0;
	while(father[mbz]){ //从目标节点往前推路径并存储到res数组中
		cnt++;
		res[cnt][0]=ans[mbz].ox,res[cnt][1]=ans[mbz].oy,res[cnt][2]=ans[mbz].nx,res[cnt][3]=ans[mbz].ny,
		mbz=father[mbz];
	}
	cout<<cnt<<endl;
	for(int i=cnt;i>=1;i--) //从起点--->终点的交换过程
		cout<<res[i][0]<<res[i][1]<<res[i][2]<<res[i][3]<<endl;
	return 0;
}

代码仅供一种思路参考（不要抄袭，没有任何意义），能够写出来AC的同学可尝试进一步使用双向bfs进行优化。