【OJ】A*(start)算法c++初步实现

<span style="font-size:14px;">/*
	A* 算法 2014/11/5 吴成兵
	改进中
	BFS是A*算法中最笨的一种
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
const int INF=888;//200
char a[11][11];

// 起点和终点可以任意修改 //坐标原点在左上角，行为y，横列为x
const int sy=1,sx=3,ey=8,ex=2;//开始（1，3） 目的（5，2） 

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//四个方向（本来是八个） 

struct FIELD{
	int f,g,h;  //h=f+g
	int y,x;    //f为开始到本地距离，g为本地到目的地距离
}b[10][10];
////priority_queue<int,vector<int>,greater<int> >pq;
//bool cmp(const FIELD &a,const FIELD &b){
//	return a.h>b.h;
//}
struct cmp{                         //用于构造逆的优先队列
	bool operator()(const FIELD a,const FIELD b)const{
		return a.h>b.h;
	}
};

void A(){
	priority_queue<FIELD,vector<FIELD>,cmp>q;
	q.push(b[sy][sx]);
	while(!q.empty()){
		FIELD f=q.top();q.pop();//FIELD
		if(f.x==ex&&f.y==ey)break;
		for(int i=0;i<4;i++){
			int nx=f.x+dx[i],ny=f.y+dy[i];
			if(nx>=0&&nx<10&&ny>=0&&ny<10&&a[ny][nx]!='#'&&b[ny][nx].h==INF/**/){
				FIELD next;     //FIELD
				/*h=f+g*/
				next.f=sqrt(pow(ny-sy,2)+pow(nx-sx,2))*10;//到起点10倍距离 //?墙
				next.g=(fabs(ny-ey)+fabs(nx-ex))*10;      //xy方向到终点10倍距离
				next.h=next.f+next.g;
				next.y=ny; next.x=nx; 

				b[ny][nx].h=next.h;//存数值
				b[ny][nx].f=next.f;//
				b[ny][nx].g=next.g;//

				q.push(next);

				if(ny!=ey||nx!=ex) //用&&会断路效应
					a[ny][nx]='.';
			}
		}
	}
}

int main(){

//	memset(b,-1,sizeof(b));
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			b[i][j].h=INF;
		}
	}
	a[3][2]=a[3][3]=a[3][4]=a[3][5]=a[3][6]=a[2][7]='#';  //栅栏可以任意修改
	a[sy][sx]='*';a[ey][ex]='$';                  //起点和终点标志
//	for(int i=0;i<11;i++)a[10][i]='-';
	for(int i=0;i<10;i++)a[i][10]='|';            //用于显示边界
	b[sy][sx].h=b[sy][sx].f=b[sy][sx].g=0;
	b[sy][sx].y=sy;b[sy][sx].x=sx;

	A();/**/
////
////	pq.push(2);
////	pq.push(12);
////	pq.push(2);
////	pq.push(32);
////	while(!pq.empty()){
////		cout<<pq.top()<<endl;
////		pq.pop();
////	}

	for(int i=0;i<10;i++){//11           //输出地图
		for(int j=0;j<11;j++)cout<<a[i][j];cout<<endl;
	}
	for(int i=0;i<10;i++){              //输出数值图
		for(int j=0;j<10;j++){
//			if(b[i][j].h==INF)cout<<"    ";
//			else
				printf("%3d",b[i][j].h);
//			cout<<i<<" "<<j<<" "<<b[i][j].f<<" "<<b[i][j].g<<" "<<b[i][j].h<<endl;
		}
		cout<<endl;
	}
	return 0;
}
</span>

**Wu_Being博客声明**：本人博客欢迎转载，请标明博客原文和原链接！谢谢！ 

《A*(start)算法c++初步实现》：

http://blog.csdn.net/u014134180/article/details/40838319

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。