cpp

main.cpp

#include <queue> // 包括队列头文件
#include <vector>
#include <iostream>

using namespace std; // 使用标准命名空间

class Solution
{
public:
    vector<vector<int>> grid;
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    int n;

    int shortestPathBinaryMatrix(vector<vector<int>> &grid)
    {
        if (grid[0][0] == 1)
        {
            return -1;
        }

        this->grid = grid;
        n = int(grid.size());
        vector<vector<bool>> seen(n, vector<bool>(n, false));
        queue<vector<int>> queue;
        seen[0][0] = true;
        queue.push({0, 0, 1}); // row, col, steps

        while (!queue.empty())
        {
            vector<int> curr = queue.front();
            queue.pop();
            int row = curr[0], col = curr[1], steps = curr[2];
            if (row == n - 1 && col == n - 1)
            {
                return steps;
            }

            for (vector<int> &direction : directions)
            {
                int nextRow = row + direction[0], nextCol = col + direction[1];
                if (valid(nextRow, nextCol) && !seen[nextRow][nextCol])
                {
                    seen[nextRow][nextCol] = true;
                    queue.push({nextRow, nextCol, steps + 1});
                }
            }
        }

        return -1;
    }

    bool valid(int row, int col)
    {
        return 0 <= row && row < n && 0 <= col && col < n && grid[row][col] == 0;
    }
};

int main()
{
    Solution solution;
    vector<vector<int>> grid = {{0, 1}, {1, 0}}; // 你可以根据需要修改这个二进制矩阵
    int result = solution.shortestPathBinaryMatrix(grid);
    cout << "The shortest path in the binary matrix is: " << result << endl;
    return 0;
}

// $ g++ main.cpp -o main.exe
// $ ./main.exe
// The shortest path in the binary matrix is: 2