AI八数码问题 Stack Overflow

#include <stdio.h>
#include <string.h>
#define M 362881

bool IsAnswer = false;
bool Ismatch[M];//标记是否已经遍历过
int tos,len;//队列指针tos,长度len
int tt[9]={1,1,2,6,24,120,720,5040,40320};
char dest[10];//目标状态
char tmap[10];
enum dir{up,down,left,right,none};

struct {
	int dir;
	int t;
}path[M];//记录路径

struct eightnum{
	char map[10];
	int x,y;
	int father;
	dir myDir;//父节点移动的方向
}num[M];
eightnum temp;

void back_push(eightnum _num)//push
{
	strcpy(num[len].map, _num.map);
	num[len].x = _num.x;
	num[len].y = _num.y;
	num[len].father = _num.father;
	num[len].myDir = _num.myDir;
	++len;
}

eightnum front_pop()//pop
{
	tos++;
	if(tos<len)
		return num[tos];
	else
		printf("Wrong about the queue!\n");
}

int getHash(char _map[])//获取hash
{
	int hash;
	int k,l;
	hash = 0;
	int count = 0; 
	for(k=0;k<9;++k){
		count = 0;
		for(l = 0 ; l < k ;++ l){
			if(_map[k]<_map[l])
				count++;
		}
		hash += count*tt[k];
	}
	return hash;
}

int ReverseNum(char _map[])//逆序数
{
	int k,l;
	int count = 0;
	for(k=0;k<9;++k){
		for(l = 0 ; l < k ;++ l){
			if(_map[k] == '0')
				continue;
			else if(_map[k]<_map[l])
				count++;
		}
	}
	return count;
}

void DFS(eightnum _tmp)//dfs
{
	getHash(_tmp.map);
	if(strcmp(_tmp.map,dest)==0){//find the answer
		IsAnswer = true;
		printf("Find the path!\n");
		return;
	}
	else if(len>=M){//flow
		printf("Above Flow!");
		return ;
	}
	else{
		//down
		if( _tmp.x != 2){
			strcpy(tmap,_tmp.map);
			char m_tmp;
			m_tmp = tmap[_tmp.x*3+_tmp.y];
			tmap[_tmp.x*3+_tmp.y] = tmap[(_tmp.x+1)*3+_tmp.y];
			tmap[(_tmp.x+1)*3+_tmp.y] = m_tmp;
			int m_hash = getHash(tmap);
			if(Ismatch[m_hash]==false){
				Ismatch[m_hash] = true;
				strcpy(temp.map,tmap);
				temp.x = _tmp.x + 1;
				temp.y = _tmp.y;
				temp.father = tos;
				temp.myDir = down;
				back_push(temp);
			}
		}
		//right
		if( _tmp.y != 2 ){
			strcpy(tmap,_tmp.map);
			char m_tmp;
			m_tmp = tmap[(_tmp.x)*3+_tmp.y];
			tmap[(_tmp.x)*3+_tmp.y]= tmap[(_tmp.x)*3+_tmp.y+1];
			tmap[(_tmp.x)*3+_tmp.y+1] = m_tmp;
			int m_hash = getHash(tmap);
			if(Ismatch[m_hash]==false){
				Ismatch[m_hash] = true;
				strcpy(temp.map,tmap);
				temp.x = _tmp.x;
				temp.y = _tmp.y+1;
				temp.father = tos;
				temp.myDir = right;
				back_push(temp);
			}
		}
		//up
		if(_tmp.x != 0){
			strcpy(tmap,_tmp.map);
			char m_tmp;
			m_tmp = tmap[_tmp.x*3+_tmp.y];
			tmap[_tmp.x*3+_tmp.y] = tmap[(_tmp.x-1)*3+_tmp.y];
			tmap[(_tmp.x-1)*3+_tmp.y] = m_tmp;
			int m_hash = getHash(tmap);
			if(Ismatch[m_hash]==false){
				Ismatch[m_hash] = true;
				strcpy(temp.map,tmap);
				temp.x = _tmp.x - 1;
				temp.y = _tmp.y;
				temp.father = tos;
				temp.myDir = up;
				back_push(temp);
			}
		}
		//left
		if( _tmp.y != 0 ){
			strcpy(tmap,_tmp.map);
			char m_tmp;
			m_tmp = tmap[_tmp.x*3+_tmp.y];
			tmap[_tmp.x*3+_tmp.y]= tmap[(_tmp.x)*3+_tmp.y-1];
			tmap[(_tmp.x)*3+_tmp.y-1] = m_tmp;
			int m_hash = getHash(tmap);
			if(Ismatch[m_hash]==false){
				Ismatch[m_hash] = true;
				strcpy(temp.map,tmap);
				temp.x = _tmp.x;
				temp.y = _tmp.y-1;
				temp.father = tos;
				temp.myDir = left;
				back_push(temp);
			}
		}
		

	}
	eightnum m_tmp = front_pop();
	DFS(m_tmp);
}


void myDisplay(char _map[]){//display
	int ii;
	for(ii=0;ii<9;++ii){
		if(0==ii%3)
			printf("\n");
		if(_map[ii] == '0')
			printf("    ");
		else
			printf("%c   ",_map[ii]);
	}
	printf("\n-----------------------------\n");
}


int main()
{
	char input[10] ;//输入
	strcpy(input,"283164705");
	strcpy(dest,"123804765");
	int i;
	tos =  -1;
	len  = 0;	
	strcpy(temp.map,input);
	printf("原始状态:\n");
	myDisplay(input);
	for(i=0;i<M;++i)
		Ismatch[i] = false;
	if( ReverseNum(input)%2 != ReverseNum(dest)%2){
		printf("Not exist the answer!\n");
		return 1;
	}
	for(i=0;i<10;++i){
		if(temp.map[i] == '0'){
			Ismatch[getHash(temp.map)] = true;
			temp.x = i/3;
			temp.y = i%3;
			temp.father=-1;
			temp.myDir = none;
			back_push(temp);
			break;
		}
	}
	eightnum _tmp = front_pop();
	DFS(_tmp);
	int kk = 0;
	if (IsAnswer){
		int ff = tos ;
		while( num[ff].father != -1){
			path[kk].dir = num[ff].myDir;
			path[kk].t =  ff;
			kk++;
			//printf("%d",num[ff].myDir);	
			ff = num[ff].father;
		}
	}	
	
	for(i=kk-1;i>=0;--i)
	{
		if(path[i].dir==0){
			printf("down-->");
			myDisplay(num[path[i].t].map);
		}
		else if(path[i].dir==1){
			printf("up-->");
			myDisplay(num[path[i].t].map);
		}
		else if(path[i].dir==2){
			printf("right-->");
			myDisplay(num[path[i].t].map);
		}
		else if(path[i].dir==3){
			printf("left-->");
			myDisplay(num[path[i].t].map);
		}
	}
	return 0;
}