写法一
#include<iostream>
#include<queue>
using namespace std;
int dir[4][2] = { {1,0},{0,-1},{0,1},{-1,0} }; //1、初始化参数,一般有方向,地图,是否访问过
char d[4] = { 'D','L','R','U' };
char a[31][51];
bool vis[30][50];
struct node //2、然后看需求是否要定义结构体,一般需要输出步数,或者要打印路径的需要定义结构题
{
int x, y; //2.1、根须需求定义结构体,一般有点的坐标,或者步数step,path
string path;
node(int xx, int yy, string pp)//2.2、定义结构体函数——赋值用
{
x = xx;
y = yy;
path = pp;
}
};
queue<node> q;
int main()
{
for (int i = 0; i < 30; i++) cin >> a[i];
vis[0][0] = true;
node no(0, 0, " ");//3、定义起点,然后把起点放入放入队列中
q.push(no);
while (!q.empty()) //4、开始搜索 q非空
{
node now = q.front(); //5、取出第一个点,然后判断为访问过,随后出队(在哪出队灵活判断)
vis[now.x][now.y] = true;
q.pop();
if (now.x == 29 && now.y == 49)//6、退出条件(一般为满足题目所求答案的条件,比如走到终点的格子处)
{
cout << now.path; //6.1、打印答案,然后break
break;
}
else //7、否则四个方向去搜
{
for (int i = 0; i < 4; i++)
{
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if (0 <= tx && tx <= 29 && 0 <= ty && ty <= 49 && !vis[tx][ty] && a[tx][ty] != '1')//8、判断是否界内&&没有访问过&&不是1
{
node n(tx, ty, now.path + d[i]);
q.push(n);//队列插入push,出队pop,集合插入insert(..),删除erase(..) //9、把新求出来的点入队
}
}
}
}
return 0;
}
写法二
#include<iostream>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
int x;
int y;
string p; //path,记录从起点(0,0)到这个点(x,y)的完整路径
};
char a[31][51]; //存地图
char k[4] = { 'D','L','R','U' };
int dir[4][2] = { {1,0},{0,-1},{0,1},{-1,0} };
int vis[30][50]; //标记。vis=1: 已经搜过,不用再搜
void bfs() {
node start; start.x = 0; start.y = 0; start.p = ""; //定义起点
vis[0][0] = 1; //标记起点被搜过
queue<node>q; q.push(start); //把第一个点放进队列,开始BFS
while (!q.empty()) {
node now = q.front(); //取出队首
q.pop();
if (now.x == 29 && now.y == 49) { //第一次达到终点,这就是字典序最小的最短路径
cout << now.p << endl; //打印路径:从(0,0)到(29,49)
return;
}
for (int i = 0; i < 4; i++) { //扩散邻居结点
node next;
next.x = now.x + dir[i][0];
next.y = now.y + dir[i][1];
if (next.x < 0 || next.x >= 30 || next.y < 0 || next.y >= 50) //越界了
continue;
if (vis[next.x][next.y] == 1 || a[next.x][next.y] == '1') //vis=1:已经搜过; a=1:是障碍
continue;
vis[next.x][next.y] = 1; //标记被搜过
next.p = now.p + k[i]; //记录完整路径:把上一个点的路径,加上这一步后,复制给下一个点
q.push(next);
}
}
}
int main() {
for (int i = 0; i < 30; i++) cin >> a[i]; //读题目给的地图数据
bfs();
}
大佬,太强了!