bsm[1].txt

八数码问题的问题

//Global constant define

#define MaxStep  5000


#include <math.h>
#include <iostream.h>

//Global varibal define

int iCurrentElement = 0, iMe ,iStep = 0;
bool bSucceed = false;

struct bsm
{
  int s[3][3];
  int me ;
  int father;
  int level;
  int posX,posY;
}  src[MaxStep],destnation;

void print(bsm dest)
{
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
			cout << dest.s[i][j] << "  ";
		cout << '\n';
	}
}

int compare(bsm src,bsm dest)
{
	for(int i=0;i<3 ; i++)
		for(int j=0; j <3 ; j++)
			if (src.s[i][j] != dest.s[i][j])
				return 0;

	return 1;
}


void copy (bsm src,bsm dest)
{
	dest.father = src.father;
	dest.level  = src.level;
	dest.posX   = src.posX;
	dest.posY   = src.posY;
	dest.me     = src.me;
	for(int i = 0 ; i < 2 ; i++)
		for(int j = 0 ; j < 2 ; j++)
			dest.s[i][j] = src.s[i][j];
}


void step(bsm temp)
{
	bool exist ;
	for(int i=0;i < 4 ; i++)
	{
		bsm dest;
		copy(temp ,dest);
		int j = ((((i+1) % 2) ? dest.posX :dest.posY) + ((i < 2 ) ? 1 : -1));
		if (j < 0 || j > 2)
		{
			continue;
		}
		else
		{
			exist = false;
			if ((i+1) % 2) 
			{
				dest.s[dest.posX][dest.posY] = dest.s[j][dest.posY];
				dest.s[j][dest.posY] = 0;
				dest.posX = j;
			}
			else
			{
				dest.s[dest.posX][dest.posY] = dest.s[dest.posX][j];
				dest.s[dest.posX][j] = 0;
				dest.posY = j;
			}

			dest.father = iMe;
			dest.level += 1;
			dest.me     = iCurrentElement;

			for (int i = iCurrentElement ; i >= 0; i--)
			{
				if(!compare(dest ,src[i]))
				{
					exist = true;
					break;
				}
			}
			if(exist)
				continue;

			copy ( dest , src[++iCurrentElement] );

			if (compare(dest,destnation))
			{
				bSucceed = true;
				break;
			}

		}
	}
}


int Init()
{

	for(int i=0;i<3 ; i++)
	{
		for(int j=0; j <3 ; j++)
		{
			destnation.s[i][j] =  ((( ( i * 3) )  + (j+1) ) % 9 );
			cin >> src[0].s[i][j];
			if (src[0].s[i][j] < 0 || src[0].s[i][j] >8)
			{
				cout <<"Are you kidding? I can only recive the number between(include) 0 and 8! " 
					 << endl;
				return 0;
			}
			if (src[0].s[i][j] == 0)
			{
				src[0].posX = i ;
				src[0].posY = j ;
			}
		}
	}

	destnation.posX   = 2 ;
	destnation.posY   = 2 ;
	destnation.level  = 0 ;
	destnation.father = -1 ;

	src[0].level  = -1 ;
	src[0].father = -1 ;
	src[0].me     = 0  ;


	print(destnation);
	print(src[0]);

	return 1;
		
}

void layout(int dest ,int myself)
{

	if(dest != -1)
		layout(src[dest].father ,src[dest].me );
	cout << "Step " << ++iStep << ':' << endl;
	print(src[myself]);

}

void main()
{
	if(!Init())
	{
		cout << "I can't initial !";
		return;
	}


	for(int j = 0 ; !bSucceed  && iCurrentElement < MaxStep ; j++)
	{
		step(src[j]);
	}

	layout(src[iCurrentElement].father ,src[iCurrentElement].me);

	cout << endl;

	print(src[0]);


}