[HAOI2008]移动玩具

[Time Gate]

https://www.luogu.org/problemnew/show/P4289

【解题思路】

这是一道很不错的题目

15 int x[24]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,1,2,4,5,6,8,9,10}; 16 int y[24]={1,2,3,7,5,6,7,11,9,10,11,15,13,14,15,4,5,6,8,9,10,12,13,14};

用x,y数组来记录可以发生的移动，如从0号格子可以跳到一号和4号，互相对应的
这是一个很重要的点

再进行广搜啦可利用map映射更加的方便，记录位置对应步数

注意如果交换后该状态的字符串已存在则不必再次搜索（即为第42行代码）
如果交换后该状态的字符串已存在则不必再次搜索（即为第42行代码）

【code】

 1 //
 2 //  main.cpp
 3 //  magicsquare
 4 //
 5 //  Created by dongzhenbo on 2019/7/9.
 6 //  Copyright © 2019 dongzhenbo. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <map>
11 #include <queue>
12 #include <cstdio>
13 #include <algorithm>
14 using namespace std;
15 int x[24]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,1,2,4,5,6,8,9,10};
16 int y[24]={1,2,3,7,5,6,7,11,9,10,11,15,13,14,15,4,5,6,8,9,10,12,13,14};
17 map <string,int> m;
18 queue <string> q;
19 int main(){
20     string s,a,b;
21     for(int i=0;i<=3;i++){
22         cin>>s;
23         a+=s;
24     }
25     for(int i=0;i<=3;i++){
26         cin>>s;
27         b+=s;
28     }
29     m[a]=0;
30     q.push(a);
31     while(!q.empty()){
32         string c=q.front();
33         q.pop();
34         if(c==b){
35             cout<<m[c];
36             return 0;
37         }
38         for(int i=0;i<24;i++){
39                 string d=c;
40                 if(d[x[i]]==d[y[i]])continue;
41                 swap(d[x[i]],d[y[i]]);
42                 if(m[d])continue;
43                 q.push(d);
44                 m[d]=m[c]+1;
45         }
46     }
47 }