最长距离问题

问题描述：

算法：

宽度优先搜索解空间

数据结构：

unordered_map,queue,vector,hash

代码

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map> 

using namespace std;
// 使用字符串编码表示不同的状态
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
typedef pair<string,int> PLL;
unordered_map<string,PLL> h;
queue<PLL> q;    // 实现宽度优先搜索的队列
vector<string> vec;
int ans;
string ans_str;

int main(){
    string x="";
    for(int i = 0 ;i < 3; i ++)
        for(int j = 0;j < 3;j ++){
            char ch;
            cin>>ch;
            x = x + ch; // 构造初始状态
        }
    h[x]={"",0};  // 初始化哈希表
    q.push({x,0});  // 初始化队列
    while(q.size()){
        auto tmp = q.front();
        string s1 = tmp.first;
        q.pop();
        int x = s1.find("0")/3,y=s1.find("0")%3;
        for(int i=0;i<4;i++){
            int u = x + dx[i],v = y + dy[i];
            string t = s1;
            if(u >=0 && u < 3 && v >=0 && v < 3){
                swap(t[x*3+y],t[u*3+v]);
                if(!h.count(t)) {
                    h[t] = {s1,tmp.second + 1};
                    q.push({t,tmp.second + 1});
                    if(h[t].second > ans) {
                        vec.clear();
                        ans = h[t].second;
                        ans_str = t;
                    }
                    else if(h[t].second == ans) vec.push_back(t);
                }
            }
        }
    }
    cout<<ans<<endl;
    vec.push_back(ans_str); // 存储所有的最优解值
    // 最优解值已经求得，需要构造最优解
    /*
        已知目标状态和起始状态如何宽度优先遍历达到目标状态
    */
    for(int i=0;i<vec.size();i++){
        string x = vec[i];
        cout<<vec[i]<<endl;
        display(x,ans);
        cout<<endl;
    }
    return 0;
}

数字华容道数量级分析
可以到达的状态数量 181,440 = O(100000)

测试样例：

算法执行过程以及最优解构造方法

hash中同时存储上一个状态字符串以及最小有效移动次数

数据结构：

pair<string,int>

代码：

void find(string a,string b){
    // 返回从a到b需要进行得操作
    int x=a.find('0')/3,y=a.find('0')%3;
    int u=b.find('0')/3,v=b.find('0')%3;
    int i;
    for(i=0 ; i<4 ;i ++){
        if(x+dx[i] == u && y+dy[i] == v) break; 
    }
    switch(i){
            case 0: cout<<"R";break;
            case 1: cout<<"U";break;
            case 2: cout<<"L";break;
            case 3: cout<<"D";break;
    }
}

void display(string x,int k){
    if(k==0) return;
    string t=h[x].first;
    display(t,k-1);
    cout<<k<<": "<<x<<"<-"<<t;
    find(t,x);
    cout<<endl;
}

输入数据

2  6  4
1  3  7
0  5  8

样例运行结果分析

31
871035462
1: 264137508<-264137058R
2: 264137580<-264137508R
3: 264130587<-264137580D
4: 264103587<-264130587L
5: 264013587<-264103587L
6: 064213587<-264013587D
7: 604213587<-064213587R
8: 614203587<-604213587U
9: 614283507<-614203587U
10: 614283570<-614283507R
11: 614280573<-614283570D
12: 610284573<-614280573D
13: 601284573<-610284573L
14: 681204573<-601284573U
15: 681274503<-681204573U
16: 681274053<-681274503L
17: 681074253<-681274053D
18: 081674253<-681074253D
19: 801674253<-081674253R
20: 871604253<-801674253U
21: 871640253<-871604253R
22: 871643250<-871640253U
23: 871643205<-871643250L
24: 871643025<-871643205L
25: 871043625<-871643025D
26: 871403625<-871043625R
27: 871430625<-871403625R
28: 871435620<-871430625U
29: 871435602<-871435620L
30: 871435062<-871435602L
31: 871035462<-871435062D

815736402
1: 264137508<-264137058R
2: 264137580<-264137508R
3: 264130587<-264137580D
4: 264103587<-264130587L
5: 264013587<-264103587L
6: 264513087<-264013587U
7: 264513807<-264513087R
8: 264513870<-264513807R
9: 264510873<-264513870D
10: 260514873<-264510873D
11: 206514873<-260514873L
12: 216504873<-206514873U
13: 216054873<-216504873L
14: 016254873<-216054873D
15: 106254873<-016254873R
16: 156204873<-106254873U
17: 156024873<-156204873L
18: 156824073<-156024873U
19: 156824703<-156824073R
20: 156824730<-156824703R
21: 156820734<-156824730D
22: 156802734<-156820734L
23: 156832704<-156802734U
24: 156832740<-156832704R
25: 156830742<-156832740D
26: 150836742<-156830742D
27: 105836742<-150836742L
28: 015836742<-105836742L
29: 815036742<-015836742U
30: 815736042<-815036742U
31: 815736402<-815736042R