迷宫寻路
这是我们的数据结构作业本加我们自己再网上找算法记录下来,不过本人比较执着画了几天时间还是把这些算法自己写出来了。总得来说网上所说的大体算法应该就有三种(BFS,DFS,A*) 这里是一个验证网址是南阳OJ的一道题这是网址 http://acm.nyis/problem/58 好了不说废话开始吧
BFS
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。 如上所示我要做的就是搜索整张,定义一个二维数组visit, visit[x][y]判断坐标x,y是否被访问,初始化visit为0都没有被访问;定义一个结构体point里面的参数有x,y,dis;其中x,y表示坐标,dis表示出发点到该节点的步数; bfs函数操作: 1,将节点添加到队列里面; 2,从队头取出节点将其访问状态设为1,判断其上下左右四个节点将符合要求的节点添加到队列中; 3,重复1,2操作直到从队列中取出的节点终点返回其dis; 具体代码如下
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 10
int x, y, a, b;
struct point
{
int x, y, dis;//x坐标y坐标步数
};
int fx[4] = { -1,1,0,0 }, fy[4] = { 0,0,-1,1 };
int bfs(int x, int y,int maze[][9])
{
queue myque;
point tp;
tp.x = x;tp.y = y;tp.dis = 0;//初始化开始节点dis设为0
myque.push(tp);
while (!myque.empty())
{
tp = myque.front();myque.pop();//从队头取节点
if (tp.x == a && tp.y == b) { return tp.dis; }//判断是否到达目的地
for (int i = 0;i < 4;i++)
{
if (tp.x + fx[i] < 9 && tp.x + fx[i] >= 0 && tp.y + fy[i] < 9 &&
tp.y + fy[i] >= 0 && maze[tp.x + fx[i]][tp.y + fy[i]] == 0)
{
point tmp;
tmp.x = tp.x + fx[i];
tmp.y = tp.y + fy[i];
tmp.dis = tp.dis + 1;
maze[tmp.x][tmp.y] = 1;//添加进队列就将该位置设为1
myque.push(tmp);
}
}
}
}
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 >> x >> y >> a >> b;
cout =0 && maze[x - 1][y] == 0) //下
{
next(x, y, x - 1, y);
}
if (y + 1 < 9 && maze[x][y + 1] == 0) //左
{
next(x, y, x, y+1);
}
if (y - 1 >=0 && maze[x][y - 1] == 0) //右
{
next(x, y, x, y-1);
}
return 0;
}
int main()
{
int t;
cin >> t;
while (t--)
{
memset(dis, 1, sizeof(dis));//初始化将dis的值设的比较大
memset(visit, 0, sizeof(visit));//初始化visit将所有值设为0
cin >> x >> y >> a >> b;
dis[x][y] = 0;
dfs(x, y);
cout = 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 |