您的代码有以下可以改进的地方[]~(￣▽￣)~*
1.逻辑错误
```cpp
if(visit[tmp]==dp||step>dp)return;
```
```
visit[tmp]=dp;
```
这两句有逻辑错误，不能正确剪枝
2.深搜回溯优化
```
if (x != 0) {
for(int i=0; i<3; i++)for(int j=0; j<3; j++)q[i][j]=mp[i][j];
swap(mp[x][y], mp[x - 1][y]);
dfs(x - 1, y, step + 1);
for(int i=0; i<3; i++)for(int j=0; j<3; j++)mp[i][j]=q[i][j];
}
```
这样写常数过大，深搜后直接再swap回来即可，如下：
```
if (x != 0&&pre!=1) {
swap(mp[x][y], mp[x - 1][y]);
dfs(x - 1, y, step + 1,2);
swap(mp[x][y], mp[x - 1][y]);
}
```
3.剪枝
原因看我发的[讨论](https://www.luogu.com.cn/discuss/787303)，代码看最下方
4.到目前为止，程序已经97分了
[记录](https://www.luogu.com.cn/record/149468190)
最后我还是用了个flag标记，如果到了目标flag=1，再结束程序。我也不知道这样写相比较您的代码为什么会有效率提升，总是971ms惊险通过
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
char q[4][4],mp[4][4],mmp[4][4];
int ans = INT_MAX,js=0,dp=0;
string goal="123804765";
/*
pre=1: from left
pre=2: from right
pre=3: from up
pre=4: from down
*/
int h(){
int cnt=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cnt+=mp[i][j]!=goal[i*3+j]-'0';
return cnt;
}
int flag=0;
void dfs(int x,int y,int step,int pre) {//123804765
// cout<<"!"<<endl;
string tmp="";
if(step>dp)return;
for(int i=0; i<3; i++)for(int j=0; j<3; j++)tmp+=mp[i][j];
if(tmp=="123804765") {
cout<<step;
flag=1;
exit(0);
}
// if(dp==step){
// if(!h())
// {
// cout<<step<<endl;
// exit(0);
// }
// return;
// }
if (x != 0&&pre!=1) {
swap(mp[x][y], mp[x - 1][y]);
dfs(x - 1, y, step + 1,2);
swap(mp[x][y], mp[x - 1][y]);
}
if (x != 2&&pre!=2) {
swap(mp[x][y], mp[x + 1][y]);
dfs(x + 1, y, step + 1,1);
swap(mp[x][y], mp[x + 1][y]);
}
if (y != 0&&pre!=3) {
swap(mp[x][y], mp[x][y - 1]);
dfs(x, y - 1, step + 1,4);
swap(mp[x][y], mp[x][y - 1]);
}
if (y != 2&&pre!=4) {
swap(mp[x][y], mp[x][y + 1]);
dfs(x, y + 1, step + 1,3);
swap(mp[x][y], mp[x][y + 1]);
}
}
int main() {
int sx, sy;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
cin >> q[i][j];
mp[i][j]=q[i][j];
mmp[i][j]=q[i][j];
if (q[i][j] == '0')sx = i, sy = j;
}
// for(dp=0;dp<=100;dp++){
// dfs(sx, sy, 0,-1);
// }
while(1){
dfs(sx, sy, 0,-1);
dp++;
if(flag){
break;
}
}
return 0;
}
```
@[爱肝大模拟的tlxjy](/user/482610)
by Phill @ 2024-03-05 20:39:09