286. Wall and gates
Tags:
Medium
Skills:
BFSMatrix
Links:
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu điền khoảng cách ngắn nhất từ ô trống (INF) đến cổng gần nhất (0) trong một matrix.
Approach
Cách tiếp cận hiệu quả là sử dụng BFS (Breadth-First Search), vì nó đảm bảo tìm được đường đi ngắn nhất trong một đồ thị không trọng số
Step-by-step
0 (cổng) và đưa chúng vào hàng đợi BFS.INF), cập nhật khoảng cách và đưa vào hàng đợi.Solution
1/**
2 Do not return anything, modify rooms in-place instead.
3 */
4function wallsAndGates(rooms: number[][]): void {
5 const rows = rooms.length;
6 const cols = rooms[0].length;
7 const INF = 2147483647;
8 const queue: [number, number][] = [];
9
10 for (let r = 0; r < rows; r++) {
11 for (let c = 0; c < cols; c++) {
12 if (rooms[r][c] === 0) {
13 queue.push([r, c])
14 }
15 }
16 }
17
18 const directions = [
19 [-1, 0], [1, 0], [0, -1], [0, 1]
20 ]
21
22 while (queue.length > 0) {
23 const [r, c] = queue.shift()!;
24
25 for (const [dr, dc] of directions) {
26 const nr = r + dr;
27 const nc = c + dc;
28
29 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] === INF) {
30 rooms[nr][nc] = rooms[r][c] + 1;
31 queue.push([nr, nc])
32 }
33 }
34 }
35};Time and space complexity
INF) chỉ được duyệt một lần, nên cũng là O(m*n).Lưu ý
nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] === INFnr >= 0 && nr < rows && nc >= 0 && nc < cols nhằm giới hạn để index không truy cập ngoài mảngrooms[nr][nc] === INF điều kiện này nhằm xác định rằng nếu không phải là walls hoặc gates thì sẽ cộng lên 1 vì để bài yêu cầu chúng mình khoảng cách từ INF đến gate