A*寻路算法

迷宫寻路算法中A*算法比BFS更高效一点！

简化搜索区域

1. 一个记录下所有被考虑来寻找最短路径的方块（称为open 列表）
2. 一个记录下不会再被考虑的方块（成为closed列表）

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<iterator>

using namespace std;
#define MAX   10

int fx[4] = { -1,1,0,0 }, fy[4] = { 0,0,-1,1 };
int sx, sy, ex, ey;
struct _NODE
{
	int x;int y;//节点坐标
	int dis;//节点的步数
	int f;//权值
};

int cmp( _NODE a,  _NODE b)
{
	return a.f < b.f;
}
int weight(int x, int y)//高级算法不会   来个曼哈顿距离计算
{
	return abs(x - sx) + abs(y - sy) + abs(x - ex) + abs(y - ey);
}

int fun_a(int maze[9][9])
{
	_NODE  sNode;
	sNode.x = sx;sNode.y = sy;sNode.dis = 0;
	sNode.f= weight(sNode.x, sNode.y);
	maze[sNode.x][sNode.y] = 1;
	list<_NODE>  mylist;
	mylist.push_back(sNode);//添加头结点
	while (!mylist.empty())
	{
	    mylist.sort(cmp);//按节点权值大小进行排序
		sNode = mylist.front();mylist.pop_front();//从链表中取出节点
		maze[sNode.x][sNode.y] = 1;//并将访问状态设为1
		if (sNode.x == ex && sNode.y == ey)
		{
			return sNode.dis;
		}
		for (int i = 0;i < 4;i++)
		{
			if (sNode.x + fx[i] < 9 && sNode.x + fx[i] >= 0 && sNode.y + fy[i] < 9 &&
				sNode.y + fy[i] >= 0 && maze[sNode.x + fx[i]][sNode.y + fy[i]] == 0)   //判断路径是否可走
			{
				_NODE  tp;
				tp.x = sNode.x + fx[i];
				tp.y = sNode.y + fy[i];
				tp.f = weight(tp.x, tp.y); //计算节点的权值
				tp.dis = sNode.dis + 1;  //更新步数
				mylist.push_back(tp);
			}
	   }
	}
	return 0;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int maze[9][9] =
		{ { 1,1,1,1,1,1,1,1,1 },
		{ 1,0,0,1,0,0,1,0,1 },
		{ 1,0,0,1,1,0,0,0,1 },
		{ 1,0,1,0,1,1,0,1,1 },
		{ 1,0,0,0,0,1,0,0,1 },
		{ 1,1,0,1,0,1,0,0,1 },
		{ 1,1,0,1,0,1,0,0,1 },
		{ 1,1,0,1,0,0,0,0,1 },
		{ 1,1,1,1,1,1,1,1,1 },
		};
		cin >> sx >> sy >> ex >> ey;
		cout << fun_a(maze) << endl;
	}
	return 0;
}