记录编号	42719	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	空格游戏	最终得分	100
用户昵称	luishenSTL没优化就成渣	是否通过	通过
代码语言	C++	运行时间	0.840 s
提交时间	2012-09-28 11:05:29	内存使用	3.13 MiB

#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;

typedef struct point{
   int x,y;
}point;

typedef struct node{
   string s;
   int step;
   point p[4];
   point pos[50];
}node;

node start;
string target;

void
output(string str){
   for(int i=0; i<4; i++) {
      for(int j=0; j<=7; j++) printf("%3d",str[i*8+j]);
      printf("\n");
   }

}

void
solve(){
   map<string,bool> m;
   map<string,bool>::iterator it;

   m[ start.s ] = true;



     start.step=0;
     node now,next;
     queue <node> q; q.push(start);
     int cnt=1;
     while(!q.empty()) {
          now = q.front(); q.pop();
          if(now.s==target) {
              printf("%d\n",now.step); return ;
          }
          for(int i=0; i<4; i++) {
              next = now; ++next.step;
              point &gap = next.p[i];
              int num = next.s[ gap.x * 8 + gap.y -1 ]; // gap 左边的数字
              if(num%10==7 || num==0) continue;
              int suc = num+1;

              point &sucp = next.pos[ suc ];
              //将gap与后驱交换位置
              swap(next.s[ gap.x * 8 + gap.y ],next.s[ sucp.x*8 + sucp.y ]);

              // 将gap的坐标与 后驱的坐标交换
              swap(next.p[i],sucp);
              it = m.find(next.s);
              if(it==m.end())  {
                  m[ next.s ] = true;
                  q.push(next);
              }
          }
     }
     puts("-1");
}

int main(){
  freopen("gap.in","r",stdin);
  freopen("gap.out","w",stdout);
  target="";
  for(int i=1; i<=4; i++) {
       for(int j=1; j<=7; j++) target+= char(i*10+j); target+=char(0);
  }


  int t=1;  //scanf("%d",&t);
  while(t--) {
      int a[5][8];  memset(a,0,sizeof(a));
      start.s="";
      for(int i=0; i<4; i++) for(int j=1; j<=7; j++) {
           scanf("%d",&a[i][j]);
           for(int k=1; k<=4; k++) {
               if(a[i][j]==k*10+1) swap(a[k-1][0],a[i][j]),start.p[k-1].x=i,start.p[k-1].y=j;
           }
      }

      for(int i=0; i<4; i++) for(int j=0; j<8; j++) {
          point tmp; tmp.x=i; tmp.y=j;
          if(a[i][j]) start.pos[ a[i][j] ]=tmp;
          start.s+=char(a[i][j]);
      }
      solve();
  } // end while
  return 0;
}