🔥前言
本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面试真题，面试、找工作完全可以来这里找机会。此外，网站内的编码主题多样化，调试功能可运用性强，可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗，快去注册开启算法百炼成神之路吧！
1、AB20 走迷宫
广度优先算法实现，充分利用邻接矩阵
题目链接：走迷宫
1.1、解题思路
本题求的是起点到最终点所需要走的最小步数，那就必然少不了邻接矩阵的使用与点移动的逻辑，而整体上是广度优先算法来实现，需要利用队列：
根据网格大小确定邻接矩阵的大小并初始化全都未被访问：
用标记数组flag来记录位置是否被访问过
使用对组pair表示横纵坐标：
纵坐标正方向用第一个变量表示，横坐标正方向用第二个变量表示
相当于点（x,y）在第四象限的移动，x在竖轴，y在横轴移动
每个位置都要进行四周的移动，因此要设计移动逻辑：
不妨定义两个数组，通过-1，0 ，1 的组合确定移动方向
访问到未被访问的坐标就把其入队并将布尔值设为true，避免重复访问
该点的距离根据起始点的距离进行加一，终点的距离就是最终结果
1.2、代码实现与注释
本题源码：
#include <iostream> #include <cstring> // 引入memset函数的头文件 #include <queue> 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 <iostream> #include<climits> // 使用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; }
上面链接中有权值不同的单源最短路详解，思路几乎一致，大家可以再去温习一波，这类题型也算是图论中的典型算法题目了。
