bashuma.rar_bashuma

#include <stdio.h> #define N 9 #define SIZE 362880 #define UP 0 #define RIGHT 1 #define DOWN 2 #define LEFT 3 #define FIXED 4 #define X_S 0 #define Y_S 2 #define VIS_S 4 #define DIR_S 5 #define PAR_S 8 #define X_MASK 0x00000003 // 0000 0000 0011 x pos mask #define Y_MASK 0x0000000c // 0000 0000 1100 y pos mask #define VIS_MASK 0x00000010 // 0000 0001 0000 visited mask #define DIR_MASK 0x000000e0 // 0000 1110 0000 direction mask #define PAR_MASK 0xffffff00 // 1111 0000 0000 depth mask #define GET_X( n ) ( ( (n)&X_MASK )>>X_S ) #define GET_Y( n ) ( ( (n)&Y_MASK )>>Y_S ) #define GET_VIS( n ) ( ( (n)&VIS_MASK )>>VIS_S ) #define GET_DIR( n ) ( ( (n)&DIR_MASK )>>DIR_S ) #define GET_PAR( n ) ( ( (n)&PAR_MASK )>>PAR_S ) #define SET_X( n,x ) ( ( (n)&=~X_MASK )|=(x<<X_S) ) #define SET_Y( n,y ) ( ( (n)&=~Y_MASK )|=(y<<Y_S) ) #define SET_VIS( n,vis ) ( ( (n)&=~VIS_MASK )|=(vis<<VIS_S) ) #define SET_DIR( n,dir ) ( ( (n)&=~DIR_MASK )|=(dir<<DIR_S) ) #define SET_PAR( n,par ) ( ( (n)&=~PAR_MASK )|=(par<<PAR_S) ) int aim[N] = { 1,2,3,4,5,6,7,8,0 }, aim_index; int table[SIZE] = {0}; int open[SIZE/2+5] = {2,2}; int ArrayToIndex( const int array[N] ); void IndexToArray( int index, int array[N] ); bool IsSolvable( int array[N] ); void UpdateTable( int index, int x, int y, int father, int dir ); void AddNewNode( int father ); void PrintPath( int index ); int main( ) { char ch; int array[N], i, x, y, index; for( i=0; i<9; ) { ch = getchar(); if( ch!=' ' ) { if( ch=='x' ) { array[i] = 0; x = i/3; y = i%3; } else array[i] = ch-'0'; i++; } } if( !IsSolvable( array ) ) printf( "unsolvable" ); else { aim_index = ArrayToIndex( aim ); index = ArrayToIndex( array ); UpdateTable( index, x, y, PAR_MASK, FIXED ); open[open[1]++] = index; while( open[1] > open[0] ) { index = open[open[0]]; if( index==aim_index ) break; open[0]++; AddNewNode( index ); } PrintPath( aim_index ); } return 0; } ////////////////////////////////////////////////////////////////////// void print( int array[N] ) { for( int i=0; i<N; i++) printf("%3d", array[i]); putchar(10); } void AddNewNode( int father ) { int x,y, p,q, dir; int array[N], index; IndexToArray( father, array ); x = GET_X( table[father] ); y = GET_Y( table[father] ); dir = GET_DIR( table[father] ); p = 3*x+y; q = -1; if( dir!=LEFT && y<2 ) { q = 3*x+y+1; array[p] = array[q]; array[q] = 0; index = ArrayToIndex( array ); if( !GET_VIS(table[index]) ) UpdateTable(index, x, y+1, father, RIGHT); } if( dir!=RIGHT && y>0 ) { if( q!=-1 ) { array[q] = array[p]; array[p] = 0; } q = 3*x+y-1; array[p] = array[q]; array[q] = 0; index = ArrayToIndex( array ); if( !GET_VIS(table[index]) ) UpdateTable(index, x, y-1, father, LEFT); } if( dir!=UP && x<2 ) { if( q!=-1 ) { array[q] = array[p]; array[p] = 0; } q = 3*(x+1)+y; array[p] = array[q]; array[q] = 0; index = ArrayToIndex( array ); if( !GET_VIS(table[index]) ) UpdateTable(index, x+1, y, father, DOWN); } if( dir!=DOWN && x>0 ) { if( q!=-1 ) { array[q] = array[p]; array[p] = 0; } q = 3*(x-1)+y; array[p] = array[q]; array[q] = 0; index = ArrayToIndex( array ); if( !GET_VIS(table[index]) ) UpdateTable(index, x-1, y, father, UP); } } void UpdateTable( int index, int x, int y, int father, int dir ) { int t; SET_VIS( t, 1 ); SET_DIR( t, dir ); SET_PAR( t, father ); SET_X( t, x ); SET_Y( t, y ); table[index] = t; if( index==aim_index ) open[open[0]] = index; else open[open[1]++] = index; } /////////////////////////////////////////////////////////////////////// int ArrayToIndex( const int array[N] ) { int i, j, t, index, pos[N]; for( i=0; i<N; i++ ) pos[ array[i] ] = i; for( i=0; i<N; i++ ) { for( t=pos[i], j=0; j<t; j++ ) if( array[j]>i ) pos[i]--; } for( index=0, i=2; i<=N; i++ ) { if( index&1 ) index = index*i +pos[i-1]; else index = index*i + i-1-pos[i-1]; } return index; } void IndexToArray( int index, int array[N] ) { int i, j, t, pos[N]={0}; for( i = N; i>1; i-- ) { t = index%i; index = index/i; if( index&1 ) pos[i-1] = t; else pos[i-1] = i-1-t; } for( i = 0; i<N; i++) { for( j = i; j>pos[i]; j-- ) array[j] = array[j-1]; array[ pos[i] ] = i; } } bool IsSolvable( int array[N] ) { int i,j, r1=0, r2=0; for( i=0; i<N; i++ ) { if( array[i] ) { for( j=0; j<i; j++ ) if( array[j]>array[i] ) r1++; } if( aim[i] ) { for( j=0; j<i; j++ ) if( aim[j]>aim[i] ) r2++; } } return !((r2-r1)%2); } void PrintPath( int index ) { if( GET_DIR( table[index] )==FIXED ) return; PrintPath( GET_PAR( table[index] ) ); char dir; switch ( GET_DIR( table[index] ) ) { case LEFT: dir = 'l'; break; case RIGHT: dir = 'r'; break; case UP: dir = 'u'; break; default: dir = 'd'; break; } printf("%c", dir ); }