934. Shortest Bridge
Tags:
Medium
Skills:
BFSDFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem - DFS & BFS
Time and space complexity
Solution
1function shortestBridge(grid: number[][]): number {
2 const n = grid.length;
3 const directions = [
4 [-1, 0], [1, 0], [0, -1], [0, 1]
5 ]
6
7 const queue: [number, number][] = [];
8 function dfs(row: number, col: number) {
9 if (row < 0 || row >= n || col < 0 || col >= n || grid[row][col] !== 1) {
10 return;
11 }
12 grid[row][col] = 2;
13 queue.push([row, col]);
14 for (const [dx, dy] of directions) {
15 dfs(row + dx, col + dy);
16 }
17 }
18
19 let found = false;
20 for (let i = 0; i < n; i++) {
21 if (found) break;
22 for (let j = 0; j < n; j++) {
23 if (grid[i][j] === 1) {
24 dfs(i, j);
25 found = true;
26 break;
27 }
28 }
29 }
30
31 let steps = 0;
32 while (queue.length > 0) {
33 const size = queue.length;
34 for (let i = 0; i < size; i++) {
35 const [x, y] = queue.shift()!;
36 for (const [dx, dy] of directions) {
37 const nx = x + dx;
38 const ny = y + dy;
39
40 if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
41 if (grid[nx][ny] === 1) {
42 return steps;
43 }
44 if (grid[nx][ny] === 0) {
45 grid[nx][ny] = 2;
46 queue.push([nx, ny]);
47 }
48 }
49 }
50 }
51 steps++
52 }
53
54 return -1;
55};1 let found = false;
2 for (let i = 0; i < n; i++) {
3 if (found) break;
4 for (let j = 0; j < n; j++) {
5 if (grid[i][j] === 1) {
6 dfs(i, j);
7 found = true;
8 break;
9 }
10 }
11 }Biến found được định nghĩa trong đoạn mã để kiểm soát việc dừng tìm kiếm hòn đảo đầu tiên. Khi bạn duyệt qua lưới để tìm một ô đất (1) thuộc hòn đảo đầu tiên, bạn chỉ cần thực hiện DFS từ ô đó một lần để đánh dấu toàn bộ hòn đảo. Sau khi tìm thấy và xử lý hòn đảo đầu tiên, không cần tiếp tục duyệt các ô còn lại trong lưới.