居然有个算法叫lee，跟我的英文名一样，如此的亲切，当然要了解一下


场景是二位矩阵（一些点是1，另一些是0，只有为1的点可以通过），然后给定一个起点和一个终点，算出起点到终点的最短距离

算法的核心其实也很简单，就是每一个点我尽量都去走一走，就像多条路线一起出发，看哪个先到，那么这条路径就是最短路径，可能唯一巧妙的地方就在于这个多条路线一起出发，关键是要这多条路径交替进行，就像以前的《仙剑奇侠传》那种回合制的游戏，你一下我一下，作者在算法中用到了队列这种数据结构，巧妙的实现了交替运行的逻辑：从队列头部拿出需要执行的点，再将这个点上下左右四个方向可达的点放到队列的尾部，直到找到目标或者没有可达路径而最终退出程序。


算法实现步骤

  1. 创建一个空队列，然后将起点入队，并且把距离记录为0，然后把节点的访问状态设置为已访问（需要一个同样的二维数组记录对应节点的访问状态）

  2. 一直循环直到队列为空

    1. 从队列的头部出队一个节点
    2. 如果这个节点是目标节点，则返回它的距离
    3. 否则，对于当前节点的四个相邻节点（上下左右）进行判断，如果是合法（值是1而且未被访问）的那么就进行入队，并且把距离加1，访问状态设置为已访问

  3. 如果所有的节点都执行过依然没有找到目标节点，说明目标节点不可达


下面是c++的具体代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include "library.h"

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// A Queue Node
struct Node {
    // (x, y) represents matrix cell coordinates, and
    // `dist` represents their minimum distance from the source
    int x, y, dist;
};

// Function to check if it is possible to go to position (row, col)
// from the current position. The function returns false if (row, col)
// is not a valid position or has a value 0 or already visited.
bool isValid(vector<vector<int>> const &mat, vector<vector<bool>> &visited,
             int row, int col) {
    return (row >= 0 && row < mat.size()) && (col >= 0 && col < mat[0].size())
           && mat[row][col] && !visited[row][col];
}

int findShortestPathLength(vector<vector<int>> &mat, pair<int, int> &src, pair<int, int> &dest) {
    // base case: invalid input
    if (mat.size() == 0 || mat[src.first][src.second] == 0 ||
        mat[dest.first][dest.second] == 0) {
        return -1;
    }

    // `M × N` matrix
    int M = mat.size();
    int N = mat[0].size();

    // 上左右下 四个方向
    int row[] = {-1, 0, 0, 1};
    int col[] = {0, -1, 1, 0};

    queue<Node> q;
    // get source cell (i, j)
    int i = src.first;
    int j = src.second;

    // construct a `M × N` matrix to keep track of visited cells
    vector<vector<bool>> visited;
    visited.resize(M, vector<bool>(N));

    // mark the source cell as visited and enqueue the source node
    visited[i][j] = true;
    q.push({i, j, 0});

    // stores length of the longest path from source to destination
    int min_dist = INT_MAX;

    while (!q.empty()) {
        // dequeue front node and process it
        Node node = q.front();
        q.pop();

        // (i, j) represents a current cell, and `dist` stores its
        // minimum distance from the source
        int i = node.x, j = node.y, dist = node.dist;

        // if the destination is found, update `min_dist` and stop
        if (i == dest.first && j == dest.second)
        {
            min_dist = dist;
            break;
        }

        // check for all four possible movements from the current cell
        // and enqueue each valid movement
        for (int k = 0; k < 4; k++)
        {
            // check if it is possible to go to position
            // (i + row[k], j + col[k]) from current position
            if (isValid(mat, visited, i + row[k], j + col[k]))
            {
                // mark next cell as visited and enqueue it
                visited[i + row[k]][j + col[k]] = true;
                q.push({ i + row[k], j + col[k], dist + 1 });
            }
        }
    }

    if (min_dist != INT_MAX) {
        return min_dist;
    }

    return -1;
}

int main() {
    vector<vector<int>> mat =
            {
                    { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
                    { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },
                    { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },
                    { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
                    { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
                    { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },
                    { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
                    { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
                    { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },
                    { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
            };

    pair<int, int> src = make_pair(0, 0);
    pair<int, int> dest = make_pair(1, 2);

    int min_dist = findShortestPathLength(mat, src, dest);
    if (min_dist != -1)
    {
        cout << "The shortest path from source to destination "
                "has length " << min_dist;
    }
    else {
        cout << "Destination cannot be reached from a given source";
    }

    return 0;
}


本文作者：oldmee
本文链接：https://oldmee.github.io/2020/06/22/lee-s-algorithm/
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。