> 文档中心 > 【算法入门&搜索法】走迷宫|单源最短路径1

【算法入门&搜索法】走迷宫|单源最短路径1


✅作者简介:热爱后端语言的大学生,CSDN内容合伙人
✨精品专栏:C++面向对象
🔥系列专栏:算法百炼成神

文章目录

  • 🔥前言
  • 1、AB20 走迷宫
    • 1.1、解题思路
    • 1.2、代码实现与注释
  • 2、AB19 【模板】单源最短路1
    • 2.1、单源最短路汇总

🔥前言

本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!

1、AB20 走迷宫

广度优先算法实现,充分利用邻接矩阵

题目链接:走迷宫

【算法入门&搜索法】走迷宫|单源最短路径1【算法入门&搜索法】走迷宫|单源最短路径1

1.1、解题思路

本题求的是起点到最终点所需要走的最小步数,那就必然少不了邻接矩阵的使用与点移动的逻辑,而整体上是广度优先算法来实现,需要利用队列:

  • 根据网格大小确定邻接矩阵的大小并初始化全都未被访问:
    • 用标记数组flag来记录位置是否被访问过
  • 使用对组pair表示横纵坐标:
    • 纵坐标正方向用第一个变量表示,横坐标正方向用第二个变量表示
    • 相当于点(x,y)在第四象限的移动,x在竖轴,y在横轴移动
  • 每个位置都要进行四周的移动,因此要设计移动逻辑:
    • 不妨定义两个数组,通过-101 的组合确定移动方向
    • 访问到未被访问的坐标就把其入队并将布尔值设为true,避免重复访问
      • 该点的距离根据起始点的距离进行加一,终点的距离就是最终结果

1.2、代码实现与注释

本题源码:

#include #include  // 引入memset函数的头文件#include using namespace std;queue<pair<int, int>> q;const int N = 1001;int  w[N][N]; // 代表矩阵中起点到各点最短距离char a[N][N]; // 用来输入*或者. (障碍和通路)bool b[N][N]; // 标志位,记录坐标是否被访问过int xs, ys, xt, yt; // s 代表起始点,t代表终点int n, m;// 注意dx和dy数组存放的数据要对应,代表着上下左右的移动方向int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 核心算法:广度优先int bfs() {    memset(w, -1, sizeof(w)); // 初始距离全部设为-1    memset(b, 0, sizeof(b));  // 初始邻接矩阵全部设为未访问    b[xs][ys] = 1;    q.push(make_pair(xs, ys));    while (!q.empty()) { int x1, y1; x1 = q.front().first, y1 = q.front().second; q.pop(); for (int i = 0; i < 4; i++) {     int x2 = x1 + dx[i], y2 = y1 + dy[i];     if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && b[x2][y2] == false &&      a[x2][y2] == '.') {  b[x2][y2] = true;  w[x2][y2] = w[x1][y1] + 1;  q.push(make_pair(x2, y2));     } }    }    return w[xt][yt] + 1;}int main() {    cin >> n >> m;    cin >> xs >> ys >> xt >> yt;    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)     cin >> a[i][j];    if (bfs() == 0) cout << "-1" << endl;    else cout << bfs();    return 0;}

重要注释:

  • 将各种矩阵与变量定义在 main 函数以外,这样可以使用无参的bfs函数,省去了传参过程
  • memset 函数常用于给存储空间快速赋值,比较典型的就是配合数组进行初始化
  • 坐标方面的细节:
    • (-1,0)、(1,0)、(0,-1)、(0,1)分别表示上移、下移、左移、右移

2、AB19 【模板】单源最短路1

之前发过单源最短路2,最短路1与之的区别在于边的权值都是1

文章链接:图论入门

2.1、单源最短路汇总

边权值相同的解题源码:

#include #include // 使用INT_MAX所需要引入的头文件const int MAX = 5001;using namespace std;int main() {    int G[MAX][MAX];    for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) {     G[i][j] = INT_MAX; }    }    int n, m;    cin >> n >> m;    int u, v;    for (int i = 1; i <= m; i++) { cin >> u >> v; G[u][v] = 1; G[v][u] = 1;    }    bool flag[MAX];    int dist[MAX];    for (int i = 1; i < MAX; i++) { dist[i] = G[1][i]; flag[i] = false;    }    dist[1] = 0;    flag[1] = true;    for (int i = 2; i < MAX; i++) { int temp = INT_MAX, index = 1; for (int j = 1; j < MAX; j++) {     if (flag[j] == false && dist[j] < temp) {  temp = dist[j];  index = j;     } } if (index != 1) {     flag[index] = true; } for (int i = 2; i < MAX; i++) {     if (flag[i] == false && G[index][i] != INT_MAX) {  if (G[index][i] + dist[index] < dist[i]) {      dist[i] = G[index][i] + dist[index];  }     } }    }    if (dist[n] == INT_MAX) { cout << -1;    } else { cout << dist[n];    }    return 0;}

上面链接中有权值不同的单源最短路详解,思路几乎一致,大家可以再去温习一波,这类题型也算是图论中的典型算法题目了。