#include "stdafx.h"
#include "搜索算法.h"

findpt::findpt(){}
findpt::~findpt(){}	

void findpt::init_queue()
{	queue=(LINK)malloc(sizeof(*queue));
	queue->node=NULL;
	queue->f=-1;
	queue->next=(LINK)malloc(sizeof(*queue));
	queue->next->f=MAXINT;
	queue->next->node=NULL;
	queue->next->next=NULL;
}

void findpt::enter_queue(TREE node,int f)
{	LINK p=queue,father,q;
	while(f>p->f)
		{ father=p; p=p->next;}
	q=(LINK)malloc(sizeof(*q));
	q->f=f,q->node=node,q->next=p;
	father->next=q;
}

TREE findpt::get_from_queue()
{	TREE bestchoice=queue->next->node;
	LINK next=queue->next->next;
	free(queue->next);
	queue->next=next;
	stack[stacktop++]=bestchoice;
	return bestchoice;
}

void findpt::freetree()
{	int i;
	LINK p;
	for (i=0;i<stacktop;i++) free(stack[i]);
	while (queue)
		{ p=queue;
		  free(p->node);
		  queue=queue->next;
		  free(p);
		}
	free(queue);
}

int findpt::judge(int x,int y)
{	int distance;
	distance=abs(end_x-x)+abs(end_y-y);
	return distance;
}

int findpt::trytile(int x,int y,TREE father)
{	TREE p=father;
	int h;
	if (map[y][x]!='0') return 1; 
	h=father->h+1;
	if (h>=dis_map[y][x]) return 1;
	dis_map[y][x]=h; 
	p=(TREE)malloc(sizeof(*p));
	p->father=father;
	p->h=father->h+1;
	p->tile=tile_num(x,y);
	enter_queue(p,p->h+judge(x,y));
	return 0;
}

int findpt::findpath()
{	TREE root;
	int i,j;
	stacktop=0;
	for (i=0;i<map_h;i++)
       for (j=0;j<map_w;j++)
         dis_map[i][j]=MAXINT;
	init_queue();
	root=(TREE)malloc(sizeof(*root));
	root->tile=tile_num(start_x,start_y);
	root->h=0;
	root->father=NULL;
	enter_queue(root,judge(start_x,start_y));
	for (;;)
		{ int x,y,child;
		  root=get_from_queue();
		  if (root==NULL)
			{*path=-1; 
			 free(root); freetree();
		     return -1;
			}
		  x=tile_x(root->tile);
		  y=tile_y(root->tile);
		  if (x==end_x && y==end_y) break;
		  child =trytile(x,  y-1,root);
		  child&=trytile(x+1,y-1,root); 
		  child&=trytile(x+1,y,  root); 
		  child&=trytile(x+1,y+1,root); 
		  child&=trytile(x,  y+1,root); 
		  child&=trytile(x-1,y+1,root);
		  child&=trytile(x-1,y,  root); 
		  child&=trytile(x-1,y-1,root);
		  if (child!=0)	free(stack[--stacktop]);
		}
	for (i=0;root;i++)
		{ path[i]=root->tile;  root=root->father;}
	path[i]=-1;
	free(root);	freetree();
	return 0;
}