信息学奥赛一本通 1453：移动玩具 | 洛谷 P4289 [HAOI2008] 移动玩具
【题目链接】
ybt 1453：移动玩具
洛谷 P4289 [HAOI2008] 移动玩具
【题目考点】
1. 广搜
2. 双向广搜
3. map
map存储键值对
由于map底层是红黑树（一种二叉搜索树），其键的类型必须可以比较，即键的类型支持"<"小于号运算符。
【解题思路】
解法1：广搜
本题以4*4二维数组作为状态，状态中包含了移动玩具的步数。
输入起始和目标状态。
设队列保存状态，将起始状态入队。
每次循环出队一个状态u uu，为当前状态。
从当前状态u uu出发，遍历二维数组中的每个位置。
如果当前位置是1，那么尝试将1向其上下左右四个方向移动，其目标移动位置必须在二维数组范围内，且目标位置为0。如果可以移动，那么将当前位置和目标位置的值交换，完成移动，得到新的状态t tt。
对于新的状态t tt，先使用vis判断该状态是否出现过。如果该状态没有出现过，则记录到达该状态经过的步数dis，将t tt状态入队。而后进行下一次循环。
当出队的状态为目标状态时，返回到达目标状态的步数，即为本题的结果。
广搜过程中需要判断某一状态是否已经出现过。本题的状态为一个4*4二维数组，因此需要记录一个4*4二维数组是否出现过。
设Node类型保存状态，其中包含一个char类型的二维数组。
需要使用一组映射记录状态是否出现过。
方法1：键类型：Node，值类型：bool
由于map的键的类型必须可以比较，即实现"<"小于号运算符。我们需要对Node类型重载小于号运算符，使得两个Node类型对象可以使用小于号运算符进行比较。
其声明格式为：
booloperator<(constNode&b)const{//...}注意：函数中的两个const必须写，这是map类的要求。
此处可以自己定义一种比较规则，即给定两个二维数组，你可以根据该规则说出哪个更大哪个更小即可。以下给出一个可行的比较规则。
可以按顺序依次比较两个状态的二维数组的每个对应位置的值。
- 如果第一个数组中取到的值小于第二个数组中取到的值，返回真。
- 如果第一个数组中取到的值大于于第二个数组中取到的值，返回假。
- 如果第一个数组和第二个数组完全相同，也返回假。
方法2：键类型：string，值类型：bool
string类已经重载了小于号运算符，可以根据字典序规则比较两个字符串。
在Node类型中，将二维数组转为string。只需要遍历二维数组，将取到的字符连接为一个字符串即可。
解法2：双向广搜
可以从起始状态和目标状态同时出发进行广搜
首先将起始和目标状态同时入队。
vis为一个map，记录一个状态来源，即该状态是从哪个状态扩展得到的
- 值为0表示该状态还没出现过。
- 值为1表示该状态是从起始状态扩展得到的。
- 值为2表示该状态是从最终状态扩展得到的。
该方法必须设一个独立的名为dis的map来记录到达一个状态的步数（无法把dis放在Node类中）。
搜索过程和广搜类似，
从当前状态u uu扩展得到一个新的状态t tt时：
如果t tt状态未出现过，那么将t tt状态的来源vis[t]设为和当前u uu状态的来源vis[u]相同。
如果t tt状态已出现过，且t tt状态的来源vis[t]和当前u uu状态的来源vis[u]不同，说明在解空间树上，从起始状态出发的路径和从目标状态出发的路径相遇。
从一个来源到u uu状态的步数为dis[u]，从另一个来源到t tt状态的步数为dis[t]，从起始状态到目标状态的总步数为dis[u]+dis[t]+1。将该值返回，即为问题的结果。
记录状态的方法，可以使用上述方法1：在Node中重载小于号运算符，而后将Node作为map的键。或使用方法2：将状态转为string，而后作为map的键。
【题解代码】
解法1：广搜+Node中重载小于号运算符
#include<bits/stdc++.h>usingnamespacestd;structNode{chara[5][5];intdis;//到达该状态的步数booloperator<(constNode&b)const{for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)if(a[i][j]!=b.a[i][j])returna[i][j]<b.a[i][j];returnfalse;}booloperator==(constNode&b)const{for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)if(a[i][j]!=b.a[i][j])returnfalse;returntrue;//两数组相同}};Node st,ed;map<Node,bool>vis;intdir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};intbfs(){queue<Node>que;que.push(st);vis[st]=true;while(!que.empty()){Node u=que.front(),t=u;//t：临时变量que.pop();if(u==ed)//使用returnu.dis;for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)if(u.a[i][j]=='1')//(i,j)位置是玩具for(intk=0;k<4;++k){intx=i+dir[k][0],y=j+dir[k][1];//(x,y)移动的目标位置if(x>=1&&x<=4&&y>=1&&y<=4&&u.a[x][y]=='0'){swap(t.a[i][j],t.a[x][y]);if(!vis[t]){vis[t]=true;t.dis=u.dis+1;que.push(t);}swap(t.a[i][j],t.a[x][y]);//将t还原为和u相同}}}return-1;//如果无解返回-1，尽管题目没有要求}intmain(){for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)cin>>st.a[i][j];for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)cin>>ed.a[i][j];cout<<bfs();return0;}解法2：双向广搜+使用string表示状态
#include<bits/stdc++.h>usingnamespacestd;structNode{chara[5][5];stringstr(){string s;for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)s.push_back(a[i][j]);returns;}};Node st,ed;map<string,int>vis,dis;intdir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};intbfs(){queue<Node>que;que.push(st);que.push(ed);vis[st.str()]=1,vis[ed.str()]=2;if(vis.size()==1)return0;//起点终点相同while(!que.empty()){Node u=que.front(),t=u;//t：临时变量que.pop();for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)if(u.a[i][j]=='1')//(i,j)位置是玩具for(intk=0;k<4;++k){intx=i+dir[k][0],y=j+dir[k][1];//(x,y)移动的目标位置if(x>=1&&x<=4&&y>=1&&y<=4&&u.a[x][y]=='0'){swap(t.a[i][j],t.a[x][y]);if(vis[t.str()]==0){vis[t.str()]=vis[u.str()];dis[t.str()]=dis[u.str()]+1;que.push(t);}elseif(vis[t.str()]!=vis[u.str()])//相遇returndis[t.str()]+dis[u.str()]+1;swap(t.a[i][j],t.a[x][y]);}}}}intmain(){for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)cin>>st.a[i][j];for(inti=1;i<=4;++i)for(intj=1;j<=4;++j)cin>>ed.a[i][j];cout<<bfs();return0;}