poj_1184_BFS（？可以不用吧，待改…

本文主要是介绍poj_1184_BFS（？可以不用吧，待改…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给一个初始序列，光标停在序列第一个位置。有6个键盘操作分别做左右移动，交换首末和加减操作，求如何用最短的操作组合数来令初始序列达到某个序列。

题目思路：

BFS。

待改——代码有点不伦不类。

代码：

#include <stdio.h>
#include <stdio.h>
#include <math.h>
//#include <time.h>
//#include <windows.h>

#define N 100000
#define MAX 1000000

typedef struct{
   int array[8];
   int c;
   int pos[6];
}QUEUE;

char flag[MAX][6][10];
int src_array[8], des_array[7], min_cnt, src, des;
QUEUE q[N];
int top, num;

int array_to_int(int a[7])
{
   int sum = 0, i;
   for(i=0;i<6;i++)
      sum = sum*10 + a[i];
   return sum;
}

void find_solution()
{
   QUEUE tq;
   int tmp,j,pos,value,f2=0;

   while(top<=num){ //取队列top，加入后续队列

      if(q[top].c > min_cnt){
         top ++;
         continue;
      }

      tq = q[top];      //判断是否更新min_cnt
      if(array_to_int(tq.array) == des){
         if(tq.c < min_cnt)
             min_cnt = tq.c;
      }
      else{
         j = 0;
         while(j<6){
            f2 = 0;
            if(tq.pos[j]){ //光标到达过的位置
                tq.c += abs(tq.array[j] - des_array[j]);
                if(tq.c > min_cnt)
                   break;
                f2 = 1;
            }
            else{
               if(tq.pos[j]!=des_array[j])
                  break;
               f2 = 1;
            }
            j++;
         }
         if(f2)
            min_cnt = tq.c;
      }

     //继续寻找可能的组合
     pos = q[top].array[6];
     tq = q[top];
     //swap0 --- 1 -- 光标状态不变，光标位置不变
     if(pos!=0 && tq.array[pos]!=tq.array[0]){
          tmp = tq.array[pos];
          tq.array[pos] = tq.array[0];
          tq.array[0] = tmp;
          value = array_to_int(tq.array);
          tq.c++;
          if(tq.c < flag[value][pos][tq.array[7]]){
             //printf("swap0\n");
             flag[value][pos][tq.array[7]] = tq.c;
             num++;
             q[num] = tq;
          }
      }
      //swap1   --- 1 --- 光标状态+6 ，光标位置不变
      tq = q[top];
      if(pos!=5 && tq.array[pos]!=tq.array[5]){
          tmp = tq.array[pos];
          tq.array[pos] = tq.array[5];
          tq.array[5] = tmp;
          if(tq.array[7]<5)
             tq.array[7]+=5;
          value = array_to_int(tq.array);
          tq.c++;
          if(tq.c < flag[value][pos][tq.array[7]]){
             //printf("swap1\n");
             flag[value][pos][tq.array[7]] = tq.c;
             num++;
             tq.pos[5] = 1;
             q[num] = tq;
          }
      }

      //left --- 3 ---光标状态不变，光标位置-1
      tq = q[top];
      if(pos!=0){
         tq.array[6] = pos-1;
         value = array_to_int(tq.array);
         tq.c ++;
         if(tq.c < flag[value][pos-1][tq.array[7]]){
            //printf("left\n");
            flag[value][pos-1][tq.array[7]] = tq.c;
            num++;
            q[num] = tq;
         }
      }
      //right --- 4 ---光标状态+1or not,光标位置+1
      tq = q[top];
      if(pos!=5){
         tq.array[6] = pos+1;
         if(tq.pos[pos+1]==0)
            tq.array[7] += 1;
         value = array_to_int(tq.array);
         tq.c ++;
         if(tq.c < flag[value][pos+1][tq.array[7]]){
            //printf("right\n");
            flag[value][pos+1][tq.array[7]] = tq.c;
            num++;
            tq.pos[pos+1] = 1;
            q[num] = tq;
         }
      }
      top ++; //头部指针后移
   }
}

main()
{
   int i, tmp1, tmp2, j, k;
   //int timebegin;
   scanf("%d %d",&src, &des);

   min_cnt = 5;
   tmp1 = src;
   tmp2 = des;
   i=0;
   while(i<6){
      src_array[5-i] = tmp1;
      tmp1 = tmp1/10;
      des_array[5-i] = tmp2;
      tmp2 = tmp2/10;
      min_cnt += fabs(src_array[5-i]-des_array[5-i]);
      i++;
   }
   for(i=0;i<MAX;i++)
      for(j=0;j<6;j++)
         for(k=0;k<10;k++)
            flag[i][j][k] = min_cnt;

   src_array[6] = 0;
   src_array[7] = 0;
   flag[array_to_int(src_array)][0][0]=1;

   top = 1;
   for(i=0;i<8;i++)
      q[top].array[i] = src_array[i];

   q[top].c = 0;
   memset(q[top].pos, 0, sizeof(q[top].pos));
   q[top].pos[0] = 1;
   num = top;

// timebegin = GetTickCount();
   find_solution();
// printf("time = %d\n",GetTickCount()-timebegin);
   printf("%d\n",min_cnt);

   system("pause");
   return 0;
}