1091.md

1091. Shortest Path in Binary Matrix

Leetcode link

解题思路

题目要求我们从给定的一个 n*n 的格子里面找出一条最短的从左上角到右下角的路径（这个路径只能由 0 构成且可以往 8 个方向走）

这种题目可以用 bfs 来做，我们把起始点当成第一层，起始点能到的地方当成第二层，以此类推

每次都遍历完同一层之后再遍历下一层，这样一来，只要碰到了右下角的格子，当前的层数就是我们要的最短路径长

C++

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int size = grid.size();
        int level = 0;
        queue<pair<int, int>> q;
        vector<vector<bool>> visited(size, vector<bool>(size, false));
        
        if(grid[0][0] == 0) {
            q.push({0, 0});
            visited[0][0] = true;
        }
        
        while(!q.empty()) {
            level++;
            int n = q.size();
            
            for(int i = 0;i < n;i++) {
                pair<int, int> node = q.front();
                q.pop();
                
                int x = node.first,
                y = node.second;
                
                if(x == size-1 && y == size-1) {
                    return level;
                }
                
                for(int j = x-1;j<=x+1;j++) {
                    for(int k = y-1;k<=y+1;k++) {
                        if(isValid(j, k, grid, visited)) {
                            q.push({j, k});
                            visited[j][k] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
    bool isValid(int x, int y, vector<vector<int>>& grid, vector<vector<bool>> &visited) {
        int size = grid.size();
        return x>=0 && x < size && y >= 0 && y < size && grid[x][y] == 0 && !visited[x][y];
    }
};

Javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function (grid) {
	let size = grid.length;
	// 记录当前元素访问状态
	let visited = new Array(size);
	for (let i = 0; i < size; i++) {
		visited[i] = new Array(size).fill(false);
	}
	// 记录当前遍历层数
	let level = 0;
	// 记录 bfs 当前状态
	let queue = [];

	if (grid[0][0] === 0) {
		queue.push([0, 0]);
		visited[0][0] = true;
	}

	while (queue.length > 0) {
		let len = queue.length;
		level++;

		for (let i = 0; i < len; i++) {
			let [x, y] = queue.shift();
			if (x === size - 1 && y === size - 1) {
				return level;
			}
			// push adjacent
			for (let j = x - 1; j <= x + 1; j++) {
				for (let k = y - 1; k <= y + 1; k++) {
					if (isValid(j, k, size, grid, visited)) {
						queue.push([j, k]);
						visited[j][k] = true;
					}
				}
			}
		}
	}
	return -1;
};

var isValid = function (x, y, size, grid, visited) {
	return (
		x >= 0 &&
		y >= 0 &&
		x < size &&
		y < size &&
		!visited[x][y] &&
		grid[x][y] === 0
	);
};