首页 > 其他分享 >BFS--宽搜求最短路径

BFS--宽搜求最短路径

时间:2022-10-26 20:02:00浏览次数:50  
标签:nx ny -- MAX BFS int second 搜求 &&


10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

#是障碍,.是通道,S是起点,G是终点

求出最短路径长度和路径

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<cstdio>

using namespace std;

typedef pair<int, int> P;

const int MAX_N = 105;
const int MAX_M = 105;

char field[MAX_N][MAX_M];
bool Visited[MAX_N][MAX_M];
int PathLength[MAX_N][MAX_M];
P Pre[MAX_N][MAX_M];

int N, M;
int sx, sy;
int dx, dy;

int Dir[4][2] = { 1,0,-1,0,0,1,0,-1 };

int bfs()
{
memset(Visited, false, sizeof(Visited));
memset(PathLength, 0, sizeof(PathLength));
queue<P> q;
q.push(P(sx, sy));
Visited[sx][sy] = true;
while (!q.empty()) {
P p = q.front(); q.pop();
if (p.first == dx && p.second == dy) {
break;
}
for (int i = 0; i < 4; i++) {
int nx = p.first + Dir[i][0];
int ny = p.second + Dir[i][1];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && !Visited[nx][ny] && field[nx][ny] != '#') {
q.push(P(nx, ny));
Visited[nx][ny] = true;
PathLength[nx][ny] = PathLength[p.first][p.second] + 1;
Pre[nx][ny] = P(p.first, p.second);
}
}
}
return PathLength[dx][dy];
}

void Print(P Cur) {
if (Cur.first == sx && Cur.second == sy) {
cout << "(" << sx << "," << sy << ")" << endl;
return;
}
Print(Pre[Cur.first][Cur.second]);
cout << "(" << Cur.first << "," << Cur.second << ")" << endl;
}

int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%s", &field[i]);
for (int j = 0; j < M; j++) {
if (field[i][j] == 'S') {
sx = i;sy = j;
}
if (field[i][j] == 'G') {
dx = i; dy = j;
}
}
}
int Result = bfs();
printf("%d\n", Result);
Print(P(dx,dy));
system("pause");
return 0;
}

BFS--宽搜求最短路径_#include

标签:nx,ny,--,MAX,BFS,int,second,搜求,&&
From: https://blog.51cto.com/u_13121994/5798305

相关文章

  • Springboot和mybatis-plus支持多数据源(多数据库)
    1、pom添加依赖<dependency><groupId>com.baomidou</groupId><artifactId>dynamic-datasource-spring-boot-starter</artifactId><version>3.5.1</version></de......
  • DFS--输出下一个数字
    题目描述JamJam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数,而是使用小写英文字母计数,他觉得这样做,会使世界更加丰富多彩。在他的计数法中,每个数字的位数都是相同的......
  • 贪心
    Saruman'sArmyTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 19615 Accepted: 9580DescriptionSarumantheWhitemustleadhisarmyalongastraig......
  • 滑窗法--0与1状态转变
    B.LectureSleeptimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputYourfriendMishkaandyouattendacalculu......
  • 尼姆博弈
    尼姆博弈:一种在博弈论中有基石作用的策略提醒:接下的分析有点烧脑描述:尼姆博弈是一个两人博弈,2名玩家轮流从数堆物品中拿取一定数量的物品,每次拿取时先选择某一堆,再从中......
  • MySQL 嵌套子查询 with子句 from子查询 in子查询 join组合
    一、适用场景和方法(1)适用场景考虑查询过程中是否存在以下情况:查询某些数据时需要分组才能得到,某些数据不需要分组就能得到或者分组条件不同;查询某些数据时需要where条......
  • 每天都可以见到的人,只有不了解才觉得正常
    罗素先生说得好:人人理应平等。实际上却远不是这样——特别是人与人有知识的差别。——王小波《长虫·草帽·细高挑》孤独恐怕就是,说的话别人迷迷糊糊,思考的问题别人......
  • 贪心--带最少的零钱
    题目描述你就要去购物了,现在你手上有N种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出1到X之间的任意值。输入格式第一行两个数X、N,以......
  • py第三方模块
    今日内容概要第三方模块的下载与使用网络爬虫模块之requests模块网络爬虫实战之爬取链家二手房数据自动化办公领域之openpyxl模块第三方模块的扩展(模块叠模块)......
  • 并查集--村村通
    题目描述某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通(但不一定有直......