317. Shortest Distance from All Buildings
Tags:
Hard
Skills:
DFSBFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bạn có một lưới 2D grid gồm các ô:
0: đất trống (có thể xây nhà)1: tòa nhà (building)2: chướng ngại vật (obstacle)Yêu cầu
Khoảng cách
Approach
Time and space complexity
Solution
1function shortestDistance(grid: number[][]): number {
2 const m = grid.length;
3 const n = grid[0].length;
4 const total_dist = Array.from({ length: m }, () => Array(n).fill(0));
5 const reach_count = Array.from({ length: m }, () => Array(n).fill(0));
6 let building_count = 0;
7 const directions = [
8 [1, 0], [-1, 0], [0, 1], [0, -1]
9 ]
10
11 for (let i = 0; i < m; i++) {
12 for (let j = 0; j < n; j++) {
13 if (grid[i][j] === 1) {
14 building_count++;
15 const visisted = Array.from({ length: m }, () => Array(n).fill(false));
16 const queue: [number, number, number][] = [[i, j, 0]]; // [row, col, dist]
17 visisted[i][j] = true
18 while (queue.length) {
19 const [x, y, dist] = queue.shift()!;
20 for (const [dx, dy] of directions) {
21 const nx = x + dx;
22 const ny = y + dy;
23
24 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visisted[nx][ny] && grid[nx][ny] === 0) {
25 visisted[nx][ny] = true;
26 total_dist[nx][ny] += dist + 1;
27 reach_count[nx][ny]++;
28 queue.push([nx, ny, dist + 1])
29 }
30 }
31 }
32 }
33 }
34 }
35
36 let min_dist = Infinity;
37 for (let i = 0; i < m; i++) {
38 for (let j = 0; j < n; j++) {
39 if (grid[i][j] === 0 && reach_count[i][j] === building_count) {
40 min_dist = Math.min(min_dist, total_dist[i][j])
41 }
42 }
43 }
44
45 return min_dist === Infinity ? -1 : min_dist
46};