PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C++语言基础(14-2)_BFS广搜法寻路

BFS广搜法寻路:

在地图内寻路,并记录下所有能达到目的地的路径,并计算路径的步数和连线次数(类似转弯次数+1)

//BFS广搜法寻路
#include <stdio.h>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
#define ROW 5
#define COL 5
struct CPos;
bool isOut(CPos pos); //是否越界
int isOK(CPos pos); //是否路通
int findQueuePos(const vector<CPos>& Node, const CPos& pos); //查找相同的
int map[ROW][COL] = {1,0,2,2,2,
 0,0,0,0,0,
 0,0,0,0,0,
 0,2,2,2,0,
 0,0,0,0,1};
bool visit[ROW][COL] = { false };
struct CPos { 
 int x, y;
 CPos(int x,int y):x(x),y(y){}
 friend ostream& operator<<(ostream& o,CPos& cpos){
 o << "(" << cpos.x << "," << cpos.y << ") ";
 return o;
 }
 bool operator==(const CPos& other) const {
 if (x == other.x && y == other.y) return true;
 return false;
 }
};
CPos pos = { 0,0 }; CPos endpos = { 4,4 };
vector <vector<CPos> > path; //每条路的路径
vector <CPos> FaNode; //当前节点 
vector <vector<int> > FaNodeWays; //当前节点 的具体路id
vector<CPos> Node; //当队列用,记录需要继续扫描的子节点
vector<CPos> tmp; //临时,用来记录当前节点的子节点坐标
int way[8] = { 0,-1,-1,0,0,1,1,0 }; //左上右下 的坐标位移
int main() {
 //从点(0,0)开始寻找到 1的路径
 //起始节点的初始化
 path.resize(1);
 path[0].push_back(pos); //第1条路径 第1个点记录
 FaNode.push_back(pos);
 FaNodeWays.resize(1);
 FaNodeWays[0].push_back(0);
 Node.push_back(pos);
 while (!Node.empty()){ //开始寻路
 pos = Node.front(); //获取队列头数据
 Node.erase(Node.begin()); //删除该数据
 visit[pos.x][pos.y] = true; //标记为已经访问过
 if (pos == endpos) //位于结束位置了。
 continue;
 //4个方向找路
 tmp.clear(); //清空临时记录表
 for (int i = 0; i < 4; ++i) {
 int x = pos.x + way[i * 2];
 int y = pos.y + way[i * 2 + 1];
 if (isOK(CPos(x, y)) != 0) 
 tmp.push_back(CPos(x, y)); //符合要求的记录下来
 }
 //将tmp里面的数据 加入队列,写到 路径,方向等等更新
 for (int i = 0; i < tmp.size(); ++i) {
 int tmp_index = 0; //tmp中的节点 和 路ID的 下标
 int index = findQueuePos(Node, tmp[i]);
 if (index == -1) {//没找到,新加 当前节点和当前节点的路ID
 Node.push_back(tmp[i]); //队列加
 FaNode.push_back(tmp[i]); //当前节点和节点路ID新加
 FaNodeWays.resize(FaNodeWays.size() + 1);
 tmp_index = FaNodeWays.size() - 1;
 }
 else { //找到了,已经存在了,找出该
 tmp_index = findQueuePos(FaNode, tmp[i]);
 }
 //找出所有当前父节点的路 复制过来,变成新路,并加1个坐标
 int FAindex = findQueuePos(FaNode, pos);
 for (int k = 0; k < FaNodeWays[FAindex].size(); ++k) {
 path.resize(path.size() + 1);
 int pathid = FaNodeWays[FAindex][k];
 for (int j = 0; j < path[pathid].size(); ++j) {
 path[path.size() - 1].push_back(path[pathid][j]);
 }
 path[path.size() - 1].push_back(tmp[i]);
 FaNodeWays[tmp_index].push_back(path.size() - 1);
 }
 }
 }

 //打印地图:
 for (int i = 0; i < ROW; ++i) {
 for (int j = 0; j < COL; ++j) {
 cout << map[i][j]<< " ";
 }
 cout << endl;
 }

 //打印所有到达结束的 路径
 int i = 0;
 while (i < path.size()) {
 if (path[i][path[i].size() - 1] == endpos) {
 cout << "步数:" << path[i].size() - 1 << " ";
 int dir = 0;
 int dirnum = 1;
 if (path[i][0].x == path[i][1].x) dir = 0;
 else dir = 1;
 cout << path[i][0];
 for (int j = 1; j < path[i].size() - 1; ++j) {
 if ((path[i][j].x == path[i][j + 1].x && dir == 1) || (path[i][j].y == path[i][j + 1].y && dir == 0)) {
 dirnum++;
 dir =(dir+1) % 2;
 }
 cout << path[i][j];
 }
 cout << path[i][path[i].size() - 1];
 cout << "连线次数:" << dirnum << endl;
 }
 ++i;
 }
 return 0;
}

bool isOut(CPos pos) { //是否越界
 if (pos.x<0 || pos.x>ROW - 1 || pos.y<0 || pos.y>COL - 1) return true;
 return false;
}
int isOK(CPos pos) { //是否路通
 if (isOut(pos)) return 0; //0表示不行
 if (map[pos.x][pos.y] == 0 && visit[pos.x][pos.y] == false) //1表示空路
 return 1;
 if (map[pos.x][pos.y] == 1 && visit[pos.x][pos.y] == false) //2表示找到目的地
 return 2;
 return 0;
}
int findQueuePos(const vector<CPos>& Node, const CPos& pos) { //查找相同的
 for (size_t i = 0; i < Node.size(); ++i) {
 if (pos == Node[i])
 return i;
 }
 return -1;
}

(2017-04-11 www.vsppc.com)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C++语言基础(14-2)_BFS广搜法寻路

分享到:更多 ()

评论 75

评论前必须登录!