Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

就这么点人过,发个AC代码把。

Posted by lx99410 at 2011-09-19 20:41:57 on Problem 1735
#include<stdio.h>
#include<string.h>
const int maxn=65536;
typedef struct node{int state,v,pre,k;node(){};
    node(int ss,int vv,int pp,int kk){state=ss;v=vv;pre=pp;k=kk;}    
}node;
node p,q[200000];
int dir[24]={49152,34816,24576,17408,12288,8704,4352,3072,2176,1536,
             1088,768,544,272,192,136,96,68,48,34,17,12,6,3};
int out[24][4]={{1,1,1,2},{1,1,2,1},{1,2,1,3},{1,2,2,2},{1,3,1,4},{1,3,2,3},
                {1,4,2,4},{2,1,2,2},{2,1,3,1},{2,2,2,3},{2,2,3,2},{2,3,2,4},
                {2,3,3,3},{2,4,3,4},{3,1,3,2},{3,1,4,1},{3,2,3,3},{3,2,4,2},
                {3,3,3,4},{3,3,4,3},{3,4,4,4},{4,1,4,2},{4,2,4,3},{4,3,4,4}
                };
char map[4][4];
bool use[maxn];
int ans[maxn][4],len,begin,end,head,tail; 
inline int abs(int a){if(a<0)a*=(-1);return a;}
void print(int now){len=0;
     printf("%d\n",q[now].v);
     while(q[now].pre!=(-1)){
       int k=q[now].k;
       for(int i=0;i<4;i++)ans[len][i]=out[k][i];
       len++;now=q[now].pre;
     }
     for(int i=len-1;i>=0;i--){
       for(int j=0;j<4;j++)printf("%d ",ans[i][j]);
       printf("\n");
     }
}
void BFS(){ 
    memset(use,0,sizeof(use));
    head=tail=0;q[tail++]=node(begin,0,-1,-1);use[begin]=1;
    while(head<tail){
      p=q[head++];
      for(int i=0;i<24;i++){
        q[tail].state=p.state^dir[i];
        if(use[q[tail].state]==0&&abs(q[tail].state-p.state)!=dir[i]){
          q[tail].pre=head-1;use[q[tail].state]=1;
          q[tail].k=i;q[tail].v=p.v+1;
          if(q[tail].state==end){print(tail);return;}tail++;
        }
      }
    }
}
int main(){
    for(int i=0;i<4;i++)scanf("%s",map[i]);
    for(int i=0;i<4;i++)
      for(int j=0;j<4;j++)
        begin=begin*2+map[i][j]-'0';
    for(int i=0;i<4;i++)scanf("%s",map[i]);
    for(int i=0;i<4;i++)
      for(int j=0;j<4;j++)
        end=end*2+map[i][j]-'0';
    if(begin==end){printf("0\n");return 0;}
    BFS();
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator