202408221300
tags: #bfs

var shortestPathBinaryMatrix = function(grid) {
	const n = grid.length;
	const DIRS = [[-1, 0], [-1, -1], [0, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [1, -1]];
	if (grid[0][0] !== 0 || grid[n - 1][n - 1] !== 0) {
		return -1;
	}
	const q = [[0, 0, 1]];
	grid[0][0] = 1;
	while (q.length > 0) {
		const [x, y, steps] = q.shift();
		if (x === n - 1 && y === n - 1) {
			return steps;
		}
		for (const [dx, dy] of DIRS) {
			const newX = x + dx;
			const newY = y + dy;
			if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] === 0) {
				grid[newX][newY] = 1;
				q.push([newX, newY, steps + 1]);
			}
		}
	}
	return -1;
};

Reference

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