桐桑入梦


私信TA

用户名:wanggongsheng

访问量:59607

签 名:

感谢你如此耀眼,做我平淡岁月里的星辰。

等  级
排  名 6
经  验 12850
参赛次数 3
文章发表 163
年  龄 20
在职情况
学  校
专  业

  自我简介:


解题思路:





注意事项:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
typedef struct node {
    int data;
    int d[10];
    int len;
    int road[100];
}node;
const int maxn = 10000;
int  A[10] ,B[10];
int hase(int *d){
     int sum=0;
     for(int i=1;i<=8;i++)
     sum=sum*10+d[i];
     return sum ;
}
int fa(int *t){
    return hase(t)/10000+hase(t)%10000*10000;
}
int fb(int *t){
    int a[10];
    a[1]=t[2];a[2]=t[3];a[3]=t[4];a[4]=t[1];
    a[5]=t[6];a[6]=t[7];a[7]=t[8];a[8]=t[5];
    return hase(a);
}
int fc(int *t){
      int a[10];
      a[1]=t[1];a[4]=t[4];a[5]=t[5];a[8]=t[8];
      a[2]=t[6];a[3]=t[2];a[6]=t[7];a[7]=t[3];
      return hase(a);
}
int main(void){
    int T;
    cin >> T;
    while(T--){
        for(int i=1;i<=4;i++) scanf("%1d",&A[i]);
        for(int i=1;i<=4;i++) scanf("%1d",&A[9-i]);
        for(int i=1;i<=4;i++) scanf("%1d",&B[i]);
        for(int i=1;i<=4;i++) scanf("%1d",&B[9-i]);
        queue<node>q;
        set<int>s;
        node a ;
        for(int i=1;i<=8;i++) a.d[i]=A[i];
        a.data = hase(A);
        a.len = 0 ;
        q.push(a);
        s.insert(a.data);
        int b_hash=hase(B);
        while(!q.empty()){
            node  x = q.front(); q.pop();
            if(x.data == b_hash){
                for(int i=0;i<x.len;i++) printf("%c",'A'+x.road[i]);
                printf("\n");
                break;
            }
            int t[10],base=10000000;
            for(int i=1;i<=8;i++){ t[i]=x.data/base%10; base /=10;}
            int a=fa(t),b =fb(t),c=fc(t);
            if(s.count(a)==0) {
                    s.insert(a);
                    node y;
                    y.data=a;
                    y.len=x.len+1;
                    memcpy(y.road,x.road,sizeof(y.road));
                    y.road[x.len]=0;
                    q.push(y);
            }
            if(s.count(b)==0) {
                    s.insert(b);
                    node y;
                    y.data=b;
                    y.len=x.len+1;
                    memcpy(y.road,x.road,sizeof(y.road));
                    y.road[x.len]=1;
                    q.push(y);
            }
            if(s.count(c)==0)  {
                    s.insert(c);
                    node y;
                    y.data=c;
                    y.len=x.len+1;
                    memcpy(y.road,x.road,sizeof(y.road));
                    y.road[x.len]=2;
                    q.push(y);
            }
        }
    }
    return 0;
}










#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef struct node {
    int data;
    int len;
    int road[100];
}node;
int s[87654321] ;
node q[1000000];
const int maxn = 10000;
int  A[10] ,B[10];
int hase(int *d){
     int sum=0;
     for(int i=1;i<=8;i++)
     sum=sum*10+d[i];
     return sum ;
}
int fa(int *t){
    return hase(t)/10000+hase(t)%10000*10000;
}
int fb(int *t){
    int a[10];
    a[1]=t[2];a[2]=t[3];a[3]=t[4];a[4]=t[1];
    a[5]=t[6];a[6]=t[7];a[7]=t[8];a[8]=t[5];
    return hase(a);
}
int fc(int *t){
      int a[10];
      a[1]=t[1];a[4]=t[4];a[5]=t[5];a[8]=t[8];
      a[2]=t[6];a[3]=t[2];a[6]=t[7];a[7]=t[3];
      return hase(a);
}
int main(void){
    int T;
    cin >> T;
    while(T--){
        memset(s,0,sizeof(s));
        for(int i=1;i<=4;i++) scanf("%1d",&A[i]);
        for(int i=1;i<=4;i++) scanf("%1d",&A[9-i]);
        for(int i=1;i<=4;i++) scanf("%1d",&B[i]);
        for(int i=1;i<=4;i++) scanf("%1d",&B[9-i]);

        node a ;
        a.data = hase(A);
        a.len = 0 ;
        q[1]=a;
        s[a.data]=1;
        int b_hash=hase(B);
        int rear=1,bottom=2;
        while(rear<bottom){
            node  x = q[rear]; rear++;
            if(x.data == b_hash){
                for(int i=0;i<x.len;i++) printf("%c",'A'+x.road[i]);
                printf("\n");
                break;
            }
            int t[10],base=10000000;
            for(int i=1;i<=8;i++){ t[i]=x.data/base%10; base /=10;}
            int a=fa(t),b =fb(t),c=fc(t);
            if(s[a]==0) {
                    s[a]=1;
                    node y=x;
                    y.data=a;
                    y.len=x.len+1;
                    y.road[x.len]=0;
                    q[bottom++]=y;
            }
            if(s[b]==0) {
                    s[b]=1;
                    node y=x;
                    y.data=b;
                    y.len=x.len+1;
                    y.road[x.len]=1;
                    q[bottom++]=y;
            }
            if(s[c]==0)  {
                    s[c]=1;
                    node y=x;
                    y.data=c;
                    y.len=x.len+1;
                    y.road[x.len]=2;
                    q[bottom++]=y;
            }
        }
    }
    return 0;
}





参考代码:

 

0.0分

0 人评分

C语言网提供「C语言、C++、算法竞赛」在线课程,全部由资深研发工程师或ACM金牌大佬亲授课,更科学、全面的课程体系,以在线视频+在线评测的学习模式学习,学练同步,拒绝理论派,真正学会编程!还有奖学金等增值福利等你!

  评论区

哥们,相信你也知道循环很占时间的,又是while又是for,要我是计算机也会爆掉!!!!!
2017-12-31 16:49:30 | |
  • «
  • 1
  • »