百度之星 2005年 初赛题目五

 

题目描述：

八方块移动游戏要求从一个含 8 个数字（用 1-8 表示）的方块以及一个空格方块（用 0 表示）的 3x3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有 3 个方向可移动。例如，假设一个 3x3 矩阵的初始状态为：

8 0 3

2 1 4

7 6 5

目标状态为：

1 2 3

8 0 4

7 6 5

则一个合法的移动路径为：

8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3

2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4

7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5

另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为 5 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。

请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用 C/C++ 实现。

输入数据：

程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态，这两个文件都由 9 个数字组成（ 0 表示空格， 1-8 表示 8 个数字方块），每行 3 个数字，数字之间用空格隔开。

输出数据：

如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出 -1 。

自测用例：

如果输入为： start.txt 和 goal.txt ，则产生的输出应为：

5

又例，如果用

7 8 4

3 5 6

1 0 2

替换 start.txt 中的内容，则产生的输出应为：

21

评分规则：

1 ）我们将首先使用和自测用例不同的 10 个 start.txt 以及相同的 goal.txt ，每个测试用例的运行时间在一台 Intel Xeon 2.80GHz 4 CPU/ 6G 内存的 Linux 机器上应不超过 10 秒（内存使用不限制），否则该用例不得分；

2 ）每个选手的总分（精确到小数点后 6 位） =10 秒钟内能产生正确结果的测试用例数量 x10+ （ 1/ 产生这些正确结果的测试用例的平均运行毫秒 ) ；

3 ）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设 N=2 ，然后重复下述过程直至产生最高的 9 位得分：用随机生成的另外 10 个有解的 start.txt 再做测试，并对这 10*N 个测试用例用 2 ）中公式重新计算总分， N++ 。

 

 

技巧说明

2	5	6
3	0	4
1	7	8

 

这是一个包含了0，1，2，3，4，5，6，7，8     九个数字的数组

九个数字，确定八个数字的位置，便可以确定两个数组是否相等，所以在保存处理的数组时可以保存前8个数字即可

 

int 在32位的机子中占用32位

 0～8 需要四位才能保持，因为前八位可能有数字8.所以保存数字至少需要4bit才能完整保存数字

因此32位可以保存8个这样的数字，即一个Int可以保存这个数字的前八位。将这样的数组保存到一个Int中

同时可以很容易根据这个int 来判断两个数组是否相同

 

 

因此，我们可以使用一个int来保存处理过的数组

 

思路介绍：

       对于某一个状态，我们可以根据0所在的位置，得到所有移动的可能性。然后将这些可能性加入到待处理队列中去。

 

      1、读取初始状态和结束状态

      2、判断是否相同，如果是返回0步

      3、处理初始状态，将所有下一步的可能状态加入到待处理队列中，将初始队列int化后，加入到已处理列表中

      4、循环处理队列

           判断取出的状态是否存在于已处理列表中

               如果是，continue;

               如果否，

                     判断是否是结束状态；若是，退出

                            如果非结束状态，将其下一步可能的状态加入到待处理队列中，将其Int化后，加入到已处理列表中

    

   

说明：在程序实现中，包含了最大步数的定义，即如果进行了N步后，仍然没找到，则推出

          实现采用的广度遍历的方法，没有使用迭代的方法处理

 

代码：

  GList.h

 

#ifndef __GLIST_H_
#define __GLIST_H_
typedef struct _Node 
{
    unsigned int data;
    struct _Node * next; 
} Node;
typedef struct _List
{
   int count; 
   Node * header;
} List;

void GListInit(List* glist);
void GListAddNode(unsigned int data,List* glist);
void GListEmptyList(List * glist);
int  GListGetCount(List* glist);
void GListPrint(List * glist);
int  GListSearch(unsigned int data,List* glist);
#endif

   

   GList.c

  

#include <stdio.h>
#include <stdlib.h>
#include "GList.h"
#include "5lib.h"
void GListInit(List* glist)
{
 	 glist->count=0;
 	 glist->header=NULL;
}
void GListAddNode(unsigned int data,List* glist)
{
    if(GListSearch(data,glist)==TRUE)
    {
		return;
    }
 	Node * node = (Node *)malloc(sizeof(Node));
 	node->data=data;
 	//node->data=(char *)strdup(data);
 	node->next=glist->header;
 	glist->header=node;
 	glist->count=glist->count+1;
}
int GetCount(List* glist)
{
 	return glist->count;
}
void FreeNode(Node * node)
{
 	 free(node);
 	 node=NULL;
}
void GListEmptyList(List * glist)
{
 	 Node* tmp;
 	 while(glist->header!=NULL)
 	 {
        tmp=glist->header;
        glist->header=tmp->next;
        //free(tmp);
        FreeNode(tmp);
     }
     glist->count=0;
     glist->header=NULL;
}

void GListPrint(List * glist)
{
 	 printf("GList:\n");
 	 Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
        printf("%u ",tmp->data);
        tmp=tmp->next;
     }
     printf("\n");
}

int GListSearch(unsigned int data,List* glist)
{
 	Node* tmp=glist->header;
 	 while(tmp!=NULL)
 	 {
	    if(data==tmp->data)
     	    return TRUE;
	    else
            tmp=tmp->next;
     }
     return FALSE;
}

 

   GQueue.h

  

#ifndef __GQUEUE_H_
#define __GQUEUE_H
typedef struct _Item
{
   int data[9];
   struct _Item * next;
} QItem;
typedef struct _Queue
{
   unsigned int count;
   QItem* header;
   QItem* tail;
} Queue;

void GQueueInit(Queue* gqueue);
void GQueuePush(int data[],Queue* gqueue);
void GQueuePop(int data[],Queue* gqueue);
void GQueueGetFirst(int data[],Queue* gqueue);
int GQueueGetSize(Queue* gqueue);
void GQueueEmpty(Queue* gqueue);
void GQueuePrint(Queue* gqueue);
#endif

 

    GQueue.c

   

#include<stdio.h>
#include<stdlib.h>
#include "GQueue.h"


void GQueueInit(Queue* gqueue)
{
 	 gqueue->count=0;
 	 gqueue->header=NULL;
 	 gqueue->tail=NULL;
}
void GQueuePush(int data[],Queue* gqueue)
{
 	 if(gqueue->count==0)
 	 {
		 QItem* item=(QItem *)malloc(sizeof(QItem));
 		 //item->data=data;
 		 int i=0;
 		 for(i=0;i<9;i++)
 		 {
			 item->data[i]=data[i];
		 }
 		 item->next=NULL;
 		 gqueue->header=item;
 		 gqueue->tail=item;
     }
     else
     {
 	    QItem* item=(QItem *)malloc(sizeof(QItem));
 	    //item->data=data;
 	     int i=0;
 		 for(i=0;i<9;i++)
 		 {
			 item->data[i]=data[i];
		 }
 	    item->next=gqueue->tail->next;
 	    gqueue->tail->next=item;
 	    gqueue->tail=item;
	 }
	 (gqueue->count)++;
}
void GQueuePop(int data[],Queue* gqueue)
{
 	 if(gqueue->header==NULL)
 	   { 
          return ;
       }
 	   QItem* item=gqueue->header;
 	   gqueue->header=item->next;
 	   (gqueue->count)--;
 	   int i=0;
 	   for(i=0;i<9;i++)
       {
			 data[i]=item->data[i];
       }
 	   free(item);
}
void GQueueGetFirst(int data[],Queue* gqueue)
{
 	   if(gqueue->header==NULL)
 	   { 
          return ;
       }
 	   int i=0;
 		for(i=0;i<9;i++)
 		{
			 data[i]=gqueue->header->data[i];
		}
}
int GQueueGetSize(Queue* gqueue)
{
 	return gqueue->count;
}
void GQueueEmpty(Queue* gqueue)
{
 	 QItem* tmp=gqueue->header;
 	 while(tmp!=NULL)
 	 {
		 gqueue->header=tmp->next;
		 free(tmp);
		 tmp=gqueue->header;
     }
     gqueue->count=0;
}

static void ArrPrint(int data[],int n)
{
 	   int i=0;
 	   for(i=0;i<n;i++)
		   printf("%d ",data[i]);
       printf("\n");
}

void GQueuePrint(Queue* gqueue)
{
 	 printf("queue count:%d\n",gqueue->count);
 	 int i=1;
 	 QItem* tmp=gqueue->header;
 	 while(tmp!=NULL)
 	 {
		 printf("%d: ",i);
		 ArrPrint(tmp->data,9); 
		 tmp=tmp->next;
		 i++;
     }
     
}

 

   5lib.h

  

#ifndef __5LIB_H_
#define __5LIB_H_
#define TRUE 1
#define FALSE 0
typedef struct _Point
{
   int x;
   int y;
   int index;
} Point;
void ArrPrint(int data[],int n);
Point LocatBlank(int arr[],int n);
unsigned int GetIntM(unsigned int source,int part);
unsigned int ArrToUInt(int a[]);
void arrcopy(int dest[],int source,int n);
#endif

 

   5lib.c

  

#include "5lib.h"
#include <stdio.h>
void ArrPrint(int data[],int n)
{
 	   int i=0;
 	   for(i=0;i<n;i++)
		   printf("%d ",data[i]);
       printf("\n");
}

Point LocatBlank(int arr[],int n)
{
 	Point result;
 	int index=-2;
 	for(int i=0;i<n;i++)
 	{
	 	if(arr[i]==0)
		{
            index=i;
			break;	
		}
    }
    result.index=index;
    index=index+1;
    if(index==-1)
    {
	   result.x=-1;
	   result.y=-1;
    }
    else if(index == 0)
    {
	 	 result.x=0;
	 	 result.y=0;
	}
    else
    {
	 	result.x=index/3;
	 	if(index%3==0)
	 	{
           result.x=result.x-1;
	 	   result.y=2;
		}
		else
	    {
		   result.y=index%3-1;	
 	    }
 	}
 	
    return result;
}

unsigned int GetIntM(unsigned int source,int part)
{
 	unsigned int def[8]={0x0000000FL,0x000000F0L,
		      0x00000F00L,0x0000F000L,
		      0x000F0000L,0x00F00000L,
		      0x0F000000L,0xF0000000L
			};
    unsigned int result=( source & (def[part-1]) ) >> ((part-1)*4);
 	return result;
}

unsigned int ArrToUInt(int a[])
{
 	unsigned int result=0x00000000L;
 	int i=0;
    for(i=0;i<8;i++)
    {
      unsigned int item=a[i];
      result=item<<(i*4)|result;
    }
    return result;
}

void arrcopy(int dest[],int source[],int n)
{
 	 if(n<=0)
 	 {
	  	return	;
     }
     int i=0;
     for (i=0;i<n;i++)
     {
	  	 dest[i]=source[i];
  	 }
}

 

   main.c

 

#include <stdio.h>
#include <stdlib.h>
#include "GQueue.h"
#include "GList.h" 
#include "5lib.h"

#define MAXLEVEL 22
List handledlist;
Queue curqueue;
Queue childqueue;
// the arr wile change to next step
void NextStep(int data[],int index,char direction)
{
 	 if('T'==direction)
 	 {
	    data[index]=data[index-3];
		data[index-3]=0;
     }
     else if ('B'==direction)
 	 {
	    data[index]=data[index+3];
		data[index+3]=0;
     }
     else if ('L'==direction)
 	 {
	    data[index]=data[index-1];
		data[index-1]=0;
     }
     else if ('R'==direction)
 	 {
	    data[index]=data[index+1];
		data[index+1]=0;
     }
}

void handlerarr(int data[],Queue* gqueue)
{
 	 int arrtmp[9];
 	 
 	 Point p=LocatBlank(data,9); 
 	 
 	 // add next steps to childqueue
 	 if(p.x==0)
 	 {
	  	arrcopy(arrtmp,data,9);
	    NextStep(arrtmp,p.index,'B');
		GQueuePush(arrtmp,gqueue);
		
     }
     else if(p.x==1)
 	 {
	  	arrcopy(arrtmp,data,9);
	  	NextStep(arrtmp,p.index,'T');
		GQueuePush(arrtmp,gqueue);
		
		arrcopy(arrtmp,data,9);
		NextStep(arrtmp,p.index,'B');
		GQueuePush(arrtmp,gqueue);
     }
     else if(p.x==2)
     {
	  	arrcopy(arrtmp,data,9);
	    NextStep(arrtmp,p.index,'T');
		GQueuePush(arrtmp,gqueue);  
     }
     
     if(p.y==0)
 	 {
        arrcopy(arrtmp,data,9);
	    NextStep(arrtmp,p.index,'R');
		GQueuePush(arrtmp,gqueue);
		
     }
     else if(p.y==1)
 	 {
        arrcopy(arrtmp,data,9);
	  	NextStep(arrtmp,p.index,'L');
		GQueuePush(arrtmp,gqueue);
		
        arrcopy(arrtmp,data,9);
		NextStep(arrtmp,p.index,'R');
		GQueuePush(arrtmp,gqueue);
     }
     else if(p.y==2)
     {
        arrcopy(arrtmp,data,9);
	    NextStep(arrtmp,p.index,'L');
		GQueuePush(arrtmp,gqueue);  
     }
     
     //save to handled list
     unsigned int arrint=ArrToUInt(data);
     GListAddNode(arrint,&handledlist);
}

int main(int argc, char *argv[])
{
  int sour[9]={7,8,4,3,5,6,1,0,2};
  int dest[9]={1,2,3,8,0,4,7,6,5};
  unsigned int sint=ArrToUInt(sour);
  unsigned int dint=ArrToUInt(dest);
  Point p=LocatBlank(dest,9);
  printf("%d %d\n",p.x,p.y);
  
  GQueueInit(&curqueue);
  GQueueInit(&childqueue);
  GListInit(&handledlist);
  
  Queue* curp=&curqueue;
  Queue* childp=&childqueue;
  
  unsigned int level=0;//to save steps's num
  if(sint==dint)
  {
    printf("after %d steps,source to destination!\n",0);
    printf("hanled count:%d\n",handledlist.count);
    printf("curp count:%d\n",curp->count);
    printf("childp count:%d\n",childp->count);
  }
  
  GQueuePush(sour,curp);
  
  while(curp->count>0)
  {
     if(level>=MAXLEVEL)
     {
		printf("out of Level\n");
		break;
     }
     printf("curp:\n");
     GQueuePrint(curp);
     printf("childp:\n");
     GQueuePrint(childp);
     printf("hanled count:%d\n",handledlist.count);
     printf("==========\n");
     
	 int data[9];//after use ,have to free
	 GQueuePop(data,curp);
	 printf("pop:");
	 ArrPrint(data,9);
	 unsigned int itemint=ArrToUInt(data);
	 if(itemint==dint)
	 {
        printf("after %d steps,source to destination!\n",level);
        break;
     }
     
	 
	 if(GListSearch(itemint,&handledlist)==FALSE)
	 {
	    //ArrPrint(
		handlerarr(data,childp);
     }
     printf("childp:\n");
     GQueuePrint(childp);
     
     if(curp->count==0)//level is end
     {
        Queue * tmp=curp;
	  	curp=childp;
		GQueueEmpty(tmp);
		childp=tmp;
		level++;	
		//printf("leve:%d",level);
		//getchar();
     }
  }
  
  system("PAUSE");	
  return 0;
}

 

 

  说明：效率貌似没想象的好，处理超过10步的移动时，发现要基本半分钟才能完成。当15步时，已经需要几分钟的时间了

 

  在获取下一步的状态是，没有引进相应的一些算法和思想，仅仅将所有的状态都处理，花费较多的时间。这里应该可以优化下