求dalao,为什么我的思路与题解差不多却只有70分(题解代码为下面注释的代码) [谢谢]
#include <iostream>
#include <cstdio>
//#include <cstdlib>
#include <algorithm>
#include <cstring>
//#include <ctime>
#include <queue>
//#include <cmath>
#include <map>
#define ovo queue<int> q;
using namespace std;
ovo
int poi=123804765;
int start=0;
int yix[4]={1,-1,0,0};
int yiy[4]={0,0,1,-1};
int arr[3][3]={0};
struct node{
int jud,bu;
};
map<int,node> m;
//int read(){
// int sum=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// sum=sum*10+ch-'0';ch=getchar();
// }
// return sum;
//}
void bfs(){
m[start].jud=1;
m[poi].jud=2;//双向应该标成两个方向
m[start].bu=0;
m[poi].bu=1;
q.push(start);
q.push(poi);
//int fafafa=start;
while(!q.empty()){
long long cur,now=q.front();q.pop();cur=now;
// if(m[now].jud==1){
// continue;
// }
// m[now].jud=1;
int x,y;
for(int i=2;i>=0;i--){
for(int j=2;j>=0;j--){
arr[i][j]=cur%10;cur/=10;//会改变值(用cur代替)
if(arr[i][j]==0){
x=i;y=j;
}
}
}
for(int k=0;k<4;k++){
long long newnum=0;
int nx=x+yix[k];
int ny=y+yiy[k];
if(nx<0||nx>2||ny<0||ny>2) continue;
swap(arr[nx][ny],arr[x][y]);
for(int i=2;i>=0;i--){
for(int j=2;j>=0;j--){
newnum=newnum*10+arr[i][j];
}
}
if(m[newnum].jud==m[now].jud){
swap(arr[nx][ny],arr[x][y]);
continue;//一定要先换回来再跳过
}
//cout << "test __> " << m[newnum].bu << " " << m[now].bu << endl;
//cout << "test __> " << fafafa << endl;//
if(m[newnum].jud+m[now].jud==3){
printf("%d",(m[newnum].bu+m[now].bu));
return ;
}
m[newnum].jud = m[now].jud;
m[newnum].bu= m[now].bu + 1;
//fafafa=now;
q.push(newnum);
swap(arr[nx][ny],arr[x][y]);
}
}
}
int main(){
freopen("aerror.txt","w",stdout);
ios::sync_with_stdio(false);
scanf("%d",&start);
if(start==poi) //特判
{
printf("0");
return 0;
}
bfs();
fclose(stdout);
return 0;
}
//273645801
//15
//
//#include<bits/stdc++.h>
//#define ll long long int
//using namespace std;
//int n,g=123804765;
//short a[4][4],fx,fy,nx,ny;
//int dx[4]={1,-1,0,0};
//int dy[4]={0,0,1,-1}; //代表向四个方向移动
//queue<int> q;
//map<int,int> v;
//map<int,int> ans;
//void solve()
//{
// if(n==g) //特判
// {
// printf("0");
// exit(0);
// }
// q.push(n); //起始状态与终止状态同时入队
// q.push(g);
// ans[n]=0;
// ans[g]=1;
// v[g]=2; //将两个方向标记成不同的数字
// v[n]=1;
// while(!q.empty())
// {
// ll now,cur=q.front();
// q.pop();
// now=cur;
// for(int i=3;i>=1;i--)
// for(int j=3;j>=1;j--)
// {
// a[i][j]=now%10,now/=10;
// if(a[i][j]==0) fx=i,fy=j;
// }
// for(int i=0;i<4;i++)
// {
// nx=fx+dx[i];
// ny=fy+dy[i];
// if(nx<1 || nx>3 || ny<1 || ny>3) continue;
// swap(a[fx][fy],a[nx][ny]);
// now=0;
// for(int p=1;p<=3;p++)
// for(int j=1;j<=3;j++)
// now=now*10+a[p][j]; //数字转矩阵
// if(v[now]==v[cur])
// {
// swap(a[fx][fy],a[nx][ny]); //一定要先换回来再跳过
// continue;
// }
// cout << "test __> " << ans[cur] << " " << ans[now] << endl;
// if(v[now]+v[cur]==3) //说明新延伸出的点已被另一方向访问过
// {
// printf("%d",ans[cur]+ans[now]);//两方向步数和即为总步数
// exit(0);
// }
// ans[now]=ans[cur]+1;
// v[now]=v[cur]; //与上一状态的方向保持一致
// q.push(now);
// swap(a[fx][fy],a[nx][ny]); //不要忘记将还回来
// }
// }
//}
//int main()
//{
// freopen("a.txt","w",stdout);
// scanf("%d",&n);
// solve();
// fclose(stdout);
//}