leetcode/algorithms/shortest_path.cpp at master · hanfezh/leetcode · GitHub

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
/*
 * =====================================================================================
 *
 *       Filename:  shortest_path.cpp
 *
 *    Description:  1091. Shortest Path in Binary Matrix
 *                  https://leetcode.com/problems/shortest-path-in-binary-matrix/
 *
 *        Version:  1.0
 *        Created:  06/29/2025 22:56:05
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xianfeng.zhu@gmail.comclass Solution {
 *   Organization:
 *
 * =====================================================================================
 */

#include <queue>
#include <utility>
#include <vector>

#include "gtest/gtest.h"

class Solution {
 public:
  int shortestPathBinaryMatrix(std::vector<std::vector<int>>& grid) {
    const int visited = -1;
    const int n = grid.size();
    if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
      return -1;
    }

    const std::vector<std::pair<int, int>> moves{{1, 1},  {0, 1},  {1, 0},  {-1, 1},
                                                 {1, -1}, {0, -1}, {-1, 0}, {-1, -1}};
    std::queue<std::pair<int, int>> q;
    int levels = 0;
    int count = 0;

    q.push({0, 0});
    grid[0][0] = visited;
    while (!q.empty()) {
      levels++;
      count = q.size();
      while (count-- > 0) {
        auto [i, j] = q.front();
        if (i == n - 1 && j == n - 1) {
          return levels;
        }

        q.pop();
        for (auto [x, y] : moves) {
          x += i;
          y += j;
          if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 0) {
            continue;
          }
          q.push({x, y});
          grid[x][y] = visited;
        }
      }
    }

    return -1;
  }
};

TEST(Solution, shortestPathBinaryMatrix) {
  std::vector<std::pair<std::vector<std::vector<int>>, int>> cases = {
      {{{0, 1}, {1, 0}}, 2},
      {{{0, 0, 0}, {1, 1, 0}, {1, 1, 0}}, 4},
      {{{1, 0, 0}, {1, 1, 0}, {1, 1, 0}}, -1},
  };
  for (auto& [grid, dist] : cases) {
    EXPECT_EQ(Solution().shortestPathBinaryMatrix(grid), dist);
  }
}