#include <Windows.h>#include <stdio.h>#include <list>#include <iostream>using namespace std;#define max_width 10#define max_height 10struct item{	int posx;	int posy;	item* parent;	item()	{		posx = 0;		posy = 0;		parent = 0;	}	~item()	{		posx = 0;		posy = 0;	}	bool operator == (item& i)	{		return (i.posx == this->posx) && (i.posy == this->posy);	}};item* g_begin;item* g_end;item* g_current;list<item*> g_openlist;list<item*> g_closelist;int g_map[max_height][max_width] ={	1,1,2,2,2,2,2,2,2,2,	1,2,2,2,2,2,2,2,2,2,	2,2,2,2,2,2,2,2,2,2,	2,2,2,1,1,1,1,1,2,2,	2,2,2,2,2,2,2,1,2,2,	2,2,2,2,2,2,2,1,2,2,	2,2,2,2,2,2,2,1,2,2,	1,1,1,2,2,2,2,2,2,2,	1,2,2,2,2,2,2,2,2,2,	2,2,2,2,2,2,1,1,2,2};void print_map(int* map,int height,int width){	for (int i = 0;i<height;i++)	{		for(int j = 0;j<width;j++)		{			if(map[i*width + j] == 1)			{				printf("*");			}			else			{				printf("@");			}			if(j == width- 1)			{				printf("\n");			}		}	}}void print_path(){}bool isinlist(item* i,list<item*> q){	list<item*>::iterator iter;	for (iter = q.begin();iter!=q.end();iter++)	{	    item* p = *iter;		if(*p == *i)		{			return true;		}	}	return false;}bool isnopath(item* i){	if(g_map[i->posy][i->posx] == 1)		return false;	else		return true;}void find_path(item* i, list<item*>& o,list<item*>& c){	if(! i)		return;	if(i->posx -1 >= 0 && i->posy -1 >=0 )	{		item*  item0 =  new item;		item0->parent = i;		item0->posx = i->posx -1;		item0->posy = i->posy -1;			if(!isinlist(item0,o) && !isinlist(item0,c) && isnopath(item0))		{			o.push_back(item0);		}	}	if(i->posy - 1 >= 0)	{		item*  item1 =  new item;		item1->parent = i;		item1->posx = i->posx;		item1->posy = i->posy -1;		if(!isinlist(item1,o) && !isinlist(item1,c) && isnopath(item1))		{			o.push_back(item1);		}		}	if(i->posx + 1 < max_width && i->posy  - 1 >= 0) 	{		item*  item2 =  new item;		item2->parent = i;		item2->posx = i->posx + 1;		item2->posy = i->posy -1;		if(!isinlist(item2,o) && !isinlist(item2,c) && isnopath(item2))		{			o.push_back(item2);		}	}	if(i->posx - 1  >= 0)	{		item*  item3 =  new item;		item3->parent = i;		item3->posx = i->posx -1;		item3->posy = i->posy;		if(!isinlist(item3,o) && !isinlist(item3,c) && isnopath(item3))		{			o.push_back(item3);		}	}	if(i->posx + 1 < max_width)	{		item*  item5 =  new item;		item5->parent = i;		item5->posx = i->posx +1;		item5->posy = i->posy ;		if(!isinlist(item5,o) && !isinlist(item5,c) && isnopath(item5))		{			o.push_back(item5);		}	}	if(i->posy + 1 < max_height && i->posx -1 >= 0)	{		item*  item6 =  new item;		item6->parent = i;		item6->posx = i->posx -1;		item6->posy = i->posy +1;		if(!isinlist(item6,o) && !isinlist(item6,c) && isnopath(item6))		{			o.push_back(item6);		}	}	if(i->posy + 1 < max_height)	{		item*  item7 =  new item;		item7->parent = i;		item7->posx = i->posx;		item7->posy = i->posy +1;		if(!isinlist(item7,o) && !isinlist(item7,c) && isnopath(item7))		{			o.push_back(item7);		}	}	if(i->posx + 1 < max_width && i->posy+1 < max_height)	{		item*  item8 =  new item;		item8->parent = i;		item8->posx = i->posx +1;		item8->posy = i->posy +1;		if(!isinlist(item8,o) && !isinlist(item8,c) && isnopath(item8))		{			o.push_back(item8);		}	}}int caculate_score(const item* stp,const item* dst){	return (dst->posx - stp->posx)*(dst->posx - stp->posx) + (dst->posy - stp->posy)*(dst->posy - stp->posy);}item* get_minscore_item(list<item*>& q){	list<item*>::iterator iter;	item* pmin = NULL;	int min = 100;	for (iter = q.begin();iter!=q.end();iter++)	{		item* p = *iter;		if(min > caculate_score(p,g_end))		{		    pmin = *iter;			min  =  caculate_score(pmin,g_end);		}	}	return pmin;}void add_item(item* i, list<item*>& q){	list<item*>::iterator iter;	bool insert = true;	for (iter = q.begin();iter!=q.end();iter++)	{		item* p = *iter;		if(*p == *i)		{			insert = false;			break;		}	}	q.push_back(i);}void delete_item(item* i, list<item*>& q){	list<item*>::iterator iter;	for (iter = q.begin();iter!=q.end();iter++)	{	    item* p = *iter;		if(*p == *i)		{			q.erase(iter);			break;		}	}}int main(char*,char**){	g_openlist.clear();	g_begin = new item;	g_begin->posx = 4;	g_begin->posy = 5;	g_end = new item;	g_end->posx =  6;	g_end->posy =  2;	g_current = new item;	g_openlist.push_back(g_begin);	while(g_openlist.size() != 0)	{		g_current = get_minscore_item(g_openlist);		if(*g_current == *g_end)		{			while(g_current)			{					if(g_current->parent)					cout<<"x:"<<g_current->posx<<"y:"<<g_current->posy<<endl;				g_current = g_current->parent;			}			break;		}		else		{			delete_item(g_current,g_openlist);			add_item(g_current,g_closelist);			find_path(g_current,g_openlist,g_closelist);         		}	}	print_map(*g_map,max_height,max_height);	return 0;}