求大优化神代码
九宫问题一、设计目的 通过实践掌握用广度优先搜索解决问题的方法。
二、问题描述
在一个3*3的九宫中，有1—8这8个数，及一个空格随机的摆放在其中的格子里。如下面左图所示。要求实现这样的问题：将九宫问题调整为如右图所示的形式。调整的规则是：每次只能将与空格（上、下或左、右）相邻的一个数字平移到空格中。
要求：问你通过移动中间的空格是否能达到右图所示的状态，如果能，则输出所走的路径，如果不能，则输出：unsolvable。最好能画出九宫的图形形式，并在其上动态的演示移动过程。
输入：包括多组测试数据，每组输入占一行，每行9个字符，表示矩阵中从左到右，从上到下的方格里的信息。
输出：对于每一组数据，输出一行，表示空格所经过的路径。
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <queue>
#include <stack>
using namespace std;
#define HashTableSize 362880
#define NOT !
#define MaxDeep 50
typedef struct maps
{
int detail[3][3];
int x, y; // 记录 空格（0）的坐标
}Map,*PMap;
Map org; // 初始状态
Map end; // 目标状态
bool HashTable[HashTableSize]={false}; //hash表
int const derection[4][2] ={ { -1 , 0 } , {1, 0 }, { 0 , -1 } , { 0, 1 } } ; // 可移动的四个方向
int Path[ MaxDeep + 1 ];
int Step;
bool Finish;
/**
*
* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）
*
**/
void input()
{
int i,j;
int sum;
for(i = 0 ; i < 9 ; i ++ )
{
scanf("%1d", *org.detail + i );
if(0 == *(*org.detail + i) )
{
org.x = i / 3;
org.y = i % 3;
}
}
for(i = 0 ; i < 9 ; i ++ ) //计算逆序
{
if( 0 == *(*org.detail + i) )
continue;
for(j = 0 ; j < i; j ++ )
if( 0 != *(*org.detail+j) && *(*org.detail + j) < *(*org.detail + i) )
{
sum ++;
}
}
if( sum%2 == 0 ) // 目标状态各个数字对应的坐标位置
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6 ;
end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0 ;
}
else
{
printf("unsolvable");
}
}
/**
*
*检测两个状态是否一样
*
**/
inline bool IsEqual(Map a , Map b)
{
return 0 == memcmp((const void *)(*a.detail),(const void *)(*b.detail),36);
}
/**
*
* hash值的计算
*
**/
int HashValue(Map a)
{
int count ;
int i , j ;
int value =0 ;
static int pv[9]={1,1,2,6,24,120,720,5040,40320};
for(i = 0 ; i < 9 ; i ++ )
{
for(j = 0, count =0 ; j < i ; j ++ )
{
if( *(*a.detail+i) < *(*a.detail+j) )
{
count ++;
}
}
value += pv[i]*count;
}
return value;
}
/**
*
* 深度优先搜索
*
**/
void Dfs(Map& node , int deep )
{
if(deep > MaxDeep )
return ;
if( true == IsEqual( node , end) )
{
Finish = true;
Step = deep;
return ;
}
for(int k =0 ;k < 4 && NOT Finish ; k ++ )
{
Map tmp = node ;
tmp.x = node.x + derection[k][0],
tmp.y = node.y + derection[k][1];
if(tmp.x < 0 || tmp.x > 2 || tmp.y <0 || tmp.y >2 )
{
continue;
}
tmp.detail[ node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ]; //移动空格
tmp.detail[ tmp.x ][ tmp.y ] = 0 ;
int tmpindex = HashValue( tmp );
if(HashTable[ tmpindex ] == true )
continue;
HashTable[ tmpindex ] = true;
Path[ deep ] = k ;
Dfs( tmp , deep + 1) ;
HashTable[ tmpindex ] = false;
}
return ;
}
/**
*
* 输出 结果
*
**/
void output()
{
Map now = org ;
int oldx,oldy;
int count =0 ;
printf("共需要 %d 步.\n", Step);
for(int i =0 ; i < 3; i ++ )
{
for(int j =0 ; j < 3; j ++)
{
printf("%3d",org.detail[ i ][ j ]);
}
printf("\n");
}
for( int k =0 ; k < Step ; k ++ )
{
oldx = now.x , oldy = now.y ;
now.x += derection[ Path[ k ] ][ 0 ], now.y += derection[ Path[ k ] ][ 1 ];
now.detail[ oldx ][ oldy ] = now.detail[ now.x ][ now.y ]; //移动空格
now.detail[ now.x ][ now.y ] = 0 ;
printf("\n ↓ 第%d步\n",++count);
getchar();
for(int i =0 ; i < 3; i ++ )
{
for(int j =0 ; j < 3; j ++)
{
printf("%3d",now.detail[ i ][ j ]);
}
printf("\n");
}
}
printf("\nThe End!\n");
}
int main()
{
input();
long time =GetTickCount();
HashTable[ HashValue( org ) ] = true;
Dfs( org , 0 );
printf("计算用时：%dMS\n",GetTickCount()-time);
output();
return 0;
}
代码如上，动态演示和九宫图形样式不会添加。
[ 本帖最后由 丨Blue丶 于 2015-6-26 09:23 编辑 ]
