求dalao,为什么我的思路与题解差不多却只有70分 [谢谢]
查看原帖
求dalao,为什么我的思路与题解差不多却只有70分 [谢谢]
113538
lowo楼主2018/10/6 22:17

求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);
//}


2018/10/6 22:17
加载中...