Leetcode 921 Shortest Path in Binary Matrix

题意：求二维矩阵中往8个方向移动的话，从左上方到右下方移动的最短路径
https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

解答：bfs易得

class Solution {
public:int shortestPathBinaryMatrix(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int ret = 0;vector<vector<int>> vis(m, vector<int>(n, 0));if(grid[0][0] == 1 || grid[m-1][n-1] == 1) {return -1;}int x[] = {1, 1, 0, -1, -1, -1, 0, 1};int y[] = {0, 1, 1, 1,   0,-1, -1 , -1};queue<pair<int, int>> q;q.push({0,0});vis[0][0] = 1;while(q.size()) {int qS = q.size();for(int i = 0; i < qS; i++) {auto node = q.front();q.pop();if (node.first == m-1 && node.second == n-1) return ret+1;for (int k = 0 ; k < 8; k++) {int dx = node.first + x[k];int dy = node.second + y[k];if(dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == 0 && vis[dx][dy] == 0) {q.push({dx,dy});vis[dx][dy] = 1;}}}ret += 1;}return -1;}
};