POJ 3221 Diamond Puzzle[bfs]

题意：

六边形被分了七块，有1到6六个数字和一个空格，每次只能交换空格和与它共边的格子里的数，求最少的交换次数，使最后达到Figure1的状态。

分析：

看到给的空间那么大，就想到是个bfs水题，hash都不需要，可是写完后作死地tle， 没办法啦，瞄了一眼discuss后，原来可以先预处理所有可以从最终状态出发的状态。  然后每输入一个都只要从表里取出来就OK啦。本来要调用n次bfs,这样就只要一次了。

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 5040
struct statt
{
  int step;
  int zero; //0的位置
  char str[9];
}start, cur, tmp, q[N];
int mov[7][5] = {{3, 2, 4, 6},{2, 2, 6}, {3, 0, 1, 3},
     {2, 2, 4}, {3, 0, 3, 5}, {2, 4, 6}, {3, 0, 1, 5}};
char seq[9];
char goal[] = "0123456";
int mark[6543211];

void swp(int a, int b)
{
  int t = tmp.str[a];
  tmp.str[a] = tmp.str[b];
  tmp.str[b] = t;
}

int to_num(char *q)
{
  int i, ret=0;
  for(i=0; i<7; i++)
  {
    ret = ret * 10 + q[i] - '0';
  }
  return ret;
}

void bfs()
{
  int m, i;
  int front = 0, rear = 0;
  q[front++] = start;
  while(rear < front)
  {
    cur = q[rear];
    rear = (rear + 1) % N;
    for(i=1; i<=mov[cur.zero][0]; i++)
    {
      strcpy(tmp.str, cur.str);
      swp(cur.zero, mov[cur.zero][i]);
      m = to_num(tmp.str);
      if(mark[m] < 0)
      {
        mark[m] = cur.step+1 ; //状态需要几步到达
        tmp.step = cur.step + 1;
        tmp.zero = mov[cur.zero][i];
        q[front] = tmp;
        front = (front + 1) % N;
      }
    }
  }
}

int main()
{
  int t, m;
  freopen("3221.in", "r",stdin);
  freopen("3221.out", "w",stdout);
  memset(mark, -1, sizeof(mark));
  
  /*预处理*/
  m = to_num(goal);
  start.step = 0;
  start.zero = 0;
  strcpy(start.str, goal);
  mark[m] = 0;
  bfs();
  
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d", &m);
    printf("%d\n", mark[m]);
    
  }
  getch();
  return 0;
}