/* -*- C -*-
*
* 8_number.c - 8数码码问题，采用A*算法，调试了5个小时左右，相当的痛苦！还是要多编程才行啊！又见指针忽悠我！
*
* Author : heixia
* Created On : Tue Mar 18 10:04:05 2008
*
*/
#include <stdio.h>
#include <stdlib.h>
#define N 3
#define MAX 5000 //寻找的最大步数,有些可能找不到结果
typedef struct num * Num;
struct num{
int depth;
int cost;
int direction; //0:up,1:down,2:left,3:right.
int i,j; //indicate the position of the blank.
int a[ N ][ N ];
Num pre;
Num father;
};
Num goal;
int n = 0;
int search(Num start);
int check( Num now,Num tobe );
void Print( Num to );
Num creatNum( Num now,int direction );
Num update( Num toupdate,Num new_num );
//main
int main( ){
int i,j;
Num start;
start = ( Num )malloc( sizeof( *start ) );
goal = ( Num )malloc( sizeof( *goal ) );
if( start == NULL || goal == NULL ){
printf( "Memory overflow.\n" );
return 0;
}
start->depth = 0;
start->direction = -1;
start->pre = NULL;
start->father = NULL;
// printf( "please input the inital state:\n" );
for(i = 0;i < N; i ++ )
for( j = 0; j < N; j ++ ){
scanf( "%d",&start->a[ i ][ j ] );
if( start->a[ i ][ j ] == -1 ){
start->i = i;
start->j = j;
}
}
// printf( "\nNow you can input the goal:\n" );
for(i = 0;i < N; i ++ )
for( j = 0; j < N; j ++ ){
scanf( "%d",&goal->a[ i ][ j ] );
}
search( start );
return 0;
}
int search(Num start){
Num current = NULL;
Num toVisit = start,new_num;
int i;
int step = 0;
while( toVisit ){
step ++;
if( step > MAX ){
printf( "Sorry,I have done what I can do.\n");
break;
}
current = toVisit;
// pr( current );
toVisit = toVisit->pre;
// pop( toVisit );
if( check( current,goal ) ){
Print( current );
return 0;
}
else {
for( i = 0; i < 4; i ++ ){
if( current->direction != i ){
new_num = creatNum( current,i );
if( new_num != NULL ){
// pr( new_num );
toVisit = update( toVisit,new_num );
// Print( toVisit );
}
}
}
}
}
//释放内存
current = toVisit;
while( current ){
toVisit = toVisit->pre;
free( current );
current = toVisit;
}
}
/*This is wrong!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
void pop( Num toVisit ){
toVisit = toVisit->pre;
}*/
int check( Num now,Num tobe ){
int **b,**c;
int i,j;
b = now->a;
c = tobe->a;
for( i = 0; i < N ;i ++ )
for( j = 0; j < N ; j ++ ){
if( now->a[ i ][ j ] != tobe->a[ i ][ j ])
return 0;
}
return 1;
}
void Print( Num to ){
int i,j;
if( to->father != NULL ){
Print( to->father );
}
for( i = 0; i < N; i ++ ){
for( j = 0; j < N ; j ++ ){
if( to->a[ i ][ j ] != -1)
printf( "%4d" ,to->a[ i ][ j ]);
else
printf( " " );
}
printf( "\n" );
}
printf( "\n" );
}
/* just for debug
void pr( Num to ){
int i,j;
for( i = 0; i < N; i ++ ){
for( j = 0; j < N ; j ++ ){
if( to->a[ i ][ j ] != -1)
printf( "%4d" ,to->a[ i ][ j ]);
else
printf( " " );
}
printf( "\n" );
}
printf( "\n" );
}
*/
Num creatNum( Num now,int direction ){
Num new_num;
int i,i_old,j,j_old,h,k,cost = 0;
int n1 = 0,n2 = 0;
i = i_old = now->i;
j = j_old = now->j;
new_num = ( Num )malloc( sizeof( *new_num ) );
switch( direction ){
case 0:i--; new_num->direction = 1; break;
case 1:i++; new_num->direction = 0; break;
case 2:j--; new_num->direction = 3; break;
case 3:j++; new_num->direction = 2; break;
default: printf( "error direction.\n" ); return NULL;
}
if( i < 0 || i >= N || j < 0 || j >= N ){
free( new_num );
return NULL;
}
for( h = 0; h < N; h ++ )
for( k = 0 ; k < N ;k ++ ){
new_num->a[ h ][ k ] = now->a[ h ][ k ];
}
new_num->a[ i_old ][ j_old ] = now->a[ i ][ j ];
new_num->a[ i ][ j ] = -1;
new_num->depth = now->depth + 1;
new_num->i = i;
new_num->j = j;
/*
for( h = 0; h < N; h ++ )
for( k = 0 ; k < N ;k ++ ){
if( new_num->a[ h ][ k ] != goal->a[ h ][ k ])
new_num->cost ++;
}
*/
if( now->a[ i_old ][ j_old ] != goal->a[ i_old ][ j_old ] )
n1++;
if( now->a[ i ][ j ] != goal->a[ i ][ j ] )
n1++;
if( new_num->a[ i_old ][ j_old ] != goal->a[ i_old ][ j_old ] )
n2++;
if( new_num->a[ i ][ j ] != goal->a[ i ][ j ] )
n2++;
new_num->cost = now->cost + ( n2 - n1 ) + 1; //+1 is because new_num->depth = now->depth + 1;
new_num->pre = NULL;
new_num->father = now;
return new_num;
}
Num update( Num toupdate,Num new_num ){
Num temp,p;
// temp = ( Num )malloc( sizeof( *temp ) ); 不需要！
// p = ( Num )malloc( sizeof( *p ) );
p = temp = toupdate;
if( toupdate != NULL ){
while( temp != NULL && temp->cost < new_num->cost ){
p = temp;
temp = temp->pre;
}
if( toupdate->cost >= new_num->cost ){
new_num->pre = toupdate;
toupdate = new_num;
}
else {
p->pre = new_num;
new_num->pre = temp;
}
}
else{
toupdate = new_num;
}
return toupdate;
}
|
