九宫重排

BFS C++ 蓝桥杯 所有文稿

题目描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

第一个图的局面记为：12345678.，第二个图的局面记为：123.46758

已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出

输出最少的步数，如果不存在方案，则输出-1。

样例输入

12345678. 
123.46758 

样例输出

3

思路：bfs，map<string,int>判重和记录步数
非常少有的一次AC了，优化什么的……

/*21:22-21:49*/
/*9:39-10:52*/
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;
map<string,int> ge;
queue<string> qu;
string u(string str,int dot){
    swap(str[dot],str[dot-3]);
    return str;
}
string d(string str,int dot){
    swap(str[dot],str[dot+3]);
    return str;
}
string l(string str,int dot){
    string str2=str.substr(0,dot-1)+'.'+str[dot-1]+str.substr(dot+1);
    return str2;
}
string r(string str,int dot){
    string str2;
    if (dot>0){str2=str.substr(0,dot-1)+str[dot-1]+str[dot+1]+'.'+str.substr(dot+2);return str2;}
    str[0]=str[1];str[1]='.';//注意 如果'.'下标为0 则下标会超出范围
    return str;
}
string (*fun[])(string str,int dot)={&u,&d,&l,&r};
void push(string str,int dot){//其实应该有简化版的。。
    int num=ge[str];
    switch(dot){
    case 0:for(int i=1;i<=3;i+=2){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    case 1:for(int i=1;i<=3;i++){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    case 2:for(int i=1;i<=2;i++){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    case 3:for(int i=0;i<=3;i++){if(i!=2){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}}break;
    case 4:for(int i=0;i<=3;i++){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    case 5:for(int i=0;i<=3;i++){if(i!=3){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}}break;
    case 6:for(int i=0;i<=3;i+=3){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    case 7:for(int i=0;i<=3;i++){if(i!=1){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}}break;
    case 8:for(int i=0;i<=2;i+=2){string str2=fun[i](str,dot);if(!ge.count(str2)) {
        ge[str2]=num+1;qu.push(str2);}}break;
    }
}
int main(){
    string s,e,str;
    int sdot;
    cin>>s>>e;
    ge[s]=0;
    qu.push(s);
    bool find=false;
    while(!qu.empty()){
        str=qu.front();
        qu.pop();
        push(str,str.find('.'));
        if (str==e) {cout<<ge[e];find=true;break;}
    }
    if (!find) cout<<-1;
    return 0;
}

据说会超时，用双向广度搜索，参考代码，（未解决）

#include <cstdio>  
#include <cstring>  
#include <string>  
#include <iostream>  
#include <queue>
#include <map>
using namespace std;  
map <string, int> M1;
map <string, int> M2;
typedef pair <string, int> P;
int dir[4] = {1, -1, 3, -3};
string s, e; // s 代表起始， e 代表结束 
bool judge(int x)
{
    if(x < 0 || x > 8) 
        return false;
    else
        return true;
}
int bfs()
{
    P pre1, nex1, pre2, nex2;
    pre1.first = s;
    pre1.second = 0;
    pre2.first = e;
    pre2.second = 0;
    queue <P> Q1; 
    queue <P> Q2;
    M1[s] = 0;
    M2[s] = 0;
    Q1.push(pre1);
    Q2.push(pre2);
    while(!Q1.empty())
    {
        pre1 = Q1.front();
        Q1.pop();
        pre2 = Q2.front();
        Q2.pop();
        string ts1 = pre1.first;
        int tn1 = pre1.second;
        string ts2 = pre2.first;
        int tn2 = pre2.second;
        int it1 = ts1.find('.');
        int it2 = ts2.find('.');
        if(ts1 == e)
        {
            return tn1;
        }
        for(int i = 0; i < 4; ++ i)
        {
            int t1 = it2 + dir[i];
            string t2 = ts2;
            char t3 = t2[it2];
            t2[it2] = t2[t1];
            t2[t1] = t3;
            int t4 = tn2 + 1;
            if((i == 0 && (it2 == 2 || it2 == 5))||(i == 1 && (it2 == 3 || it2 == 6)))
                continue;
            if(judge(t1))
            {
                if(M2[t2])
                    continue;
                M2[t2] = tn2 + 1;
                if(M1[t2])
                    return M1[t2] + M2[t2];
                nex2.first = t2;
                nex2.second = t4;
                Q2.push(nex2);
            }
        }
        for(int i = 0; i < 4; ++ i)
        {
            int t1 = it1 + dir[i];
            string t2 = ts1;
            char t3 = t2[it1];
            t2[it1] = t2[t1];
            t2[t1] = t3;
            int t4 = tn1 + 1;
            if((i == 0 && (it1 == 2 || it1 == 5))||(i == 1 && (it1 == 3 || it1 == 6)))
                continue;
            if(judge(t1))
            {
                if(M1[t2])
                    continue;
                M1[t2] = tn1 + 1;
                if(M2[t2])
                    return M1[t2] + M2[t2];
                nex1.first = t2;
                nex1.second = t4;
                Q1.push(nex1);
            }
        }
    }
    return -1;
} 
int main()  
{  
    int ans;
    cin >> s >> e;
    ans = bfs();
    if(ans == -1)
        cout << "-1" << endl;
    else
        cout << ans << endl;
    return 0;  
}   

2019.3.23