广度优先搜索

广度优先搜索典中典的题目：

在某某图/迷宫中移动

https://leetcode.cn/problems/shortest-path-in-binary-matrix/

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> vis(n, vector<bool> (n, 0));
        if (grid[0][0] == 1) return -1;
        if (n == 1) {
            return 1;
        }
        queue<tuple<int, int, int>> q;
        q.push({0, 0, 1});
        while (!q.empty()) {
            auto tp = q.front(); q.pop();
            for (auto d : dirs) {
                int dx = d[0], dy = d[1];
                int x = get<0>(tp) + dx;
                int y = get<1>(tp) + dy;
                if (0 <= x && x < n && 0 <= y && y < n && vis[x][y] == 0 && grid[x][y] == 0) {
                    vis[x][y] = 1;
                    if (x == n - 1 && y == n - 1) return get<2>(tp) + 1;
                    else {
                        q.push({x, y, get<2>(tp) + 1});
                    }
                }
            }
        }
        return -1;
    }

private:
    vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
};

private

广搜变形