蓝桥杯的一道题，做了半天只能通过部分。不知道问题出在哪里。求大神指点

问题描述

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


  我们把第一个图的局面记为：12345678.
  把第二个图的局面记为：123.46758
  显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
  本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

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

输出格式

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

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22


我的代码：


#include<iostream>
#include<string>
#include<queue>
#include<set>
using namespace std;
struct node{
    string s;
    int n;
    node(string ss,int m){
        s=ss;
        n=m;
    }
};
string s1,s2;
queue <node> q;
set<string> s;
void f(string& s,int x,int y){
    char ch=s[x];
    s[x]=s[y];
    s[y]=ch;
}
int find(string ss){
    int len=ss.length();
    for(int i=0;i<len;i++){
        if(ss[i]=='.')
            return i;
    }
}
int bfs(){
    q.push(node(s1,0));
    s.insert(s1);
    string s3,s4;
    int n;
    while(!q.empty()){
        s3=q.front().s;
        n=q.front().n;
        q.pop();
        int x=find(s3);
        if(x-3>=0){
            s4=s3;
            f(s4,x,x-3);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                q.push(node(s4,n+1));
                s.insert(s4);
            }
        }
        if(x-1>=0){
            s4=s3;
            f(s4,x,x-1);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
        if(x+3<=8){
            s4=s3;
            f(s4,x,x+3);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
        if(x+1<=8){
            s4=s3;
            f(s4,x,x+1);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
    }
    return -1;
}
int main(){
    cin>>s1>>s2;
    cout<<bfs()<<endl;
    s2=s1;
    return 0;
}

谢谢了

好像是移动块的游戏，每次只能与空白交换，如何用22步完成？

[此贴子已经被作者于2020-3-7 08:25编辑过]

不知道，程序给的样例就是这么多

这可不可以用深度优先搜索呀

我写一下代码

你用广度太复杂了

不知道是对是错，应该思路是对的额

#include<bits/stdc++.h>
using namespace std;
char m[3][3],t[3][3]; 
int a,b,ans;
void search(){
    for(int i=0;i<3;i++)
        for(int j=0;j<3;i++)
            if(m[i][j]=='.')
                {a=i;b=j;}
}
bool testsame(){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(m[i][j]!=t[i][j])return false;
        }
    }
    return true;
}
void dfs(int x,int y,int d,int cnt){
    if(testsame()){
        ans=cnt;
        return;
    }
    if(d==0){
        m[x][y]=m[x-1][y];
        m[x-1][y]='.';
    }
    if(d==1){
        m[x][y]=m[x+1][y];
        m[x+1][y]='.';
    }
    if(d==2){
        m[x][y]=m[x][y-1];
        m[x][y-1]='.';
    }
    if(d==3){
        m[x][y]=m[x][y+1];
        m[x][y+1]='.';
    }
    search();
    if(a!=0)dfs(a-1,b,0,cnt+1);
    if(a!=3)dfs(a+1,b,1,cnt+1);
    if(b!=0)dfs(a,b-1,2,cnt+1);
    if(b!=3)dfs(a,b+1,3,cnt+1);
}
int main(){
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(i==0)cin>>t[j][k];
                if(i==1)cin>>m[j][k];
            }
        }
    }
    search();
    if(a!=0)dfs(a-1,b,0,0);
    if(a!=3)dfs(a+1,b,1,0);
    if(b!=0)dfs(a,b-1,2,0);
    if(b!=3)dfs(a,b+1,3,0);
    cout<<ans;
    return 0;
} 

我写的比较暴力，可能慢了点

时间复杂度是O(n^4)还真的挺慢

我用了一点点剪枝，应该快一点