2850. Minimum Moves to Spread Stones Over Grid
Tags:
Hard
Skills:
Bit-maskDPbacktrack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
Solution - Backtracking
1function minimumMoves(grid: number[][]): number {
2 // Tính khoảng cách Manhattan giữa hai ô
3 const calculateDistance = (a: [number, number], b: [number, number]): number => {
4 return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
5 };
6
7 // Hàm đệ quy để tìm số bước tối thiểu
8 const dfs = (left: [number, number][], right: [number, number][]): number => {
9 if (left.length === 0) return 0; // Nếu không còn ô nào cần đá
10
11 let minMoves = Infinity;
12
13 for (let i = 0; i < right.length; i++) {
14 for (let j = 0; j < left.length; j++) {
15 // Tạo danh sách mới sau khi ghép đá từ right[i] vào left[j]
16 const newRight = [...right.slice(0, i), ...right.slice(i + 1)];
17 const newLeft = [...left.slice(0, j), ...left.slice(j + 1)];
18 const moves = calculateDistance(right[i], left[j]) + dfs(newLeft, newRight);
19 minMoves = Math.min(minMoves, moves);
20 }
21 }
22
23 return minMoves;
24 };
25
26 // Xác định các ô thiếu đá (left) và dư đá (right)
27 const left: [number, number][] = [];
28 const right: [number, number][] = [];
29 for (let i = 0; i < 3; i++) {
30 for (let j = 0; j < 3; j++) {
31 if (grid[i][j] === 0) left.push([i, j]);
32 if (grid[i][j] > 1) {
33 for (let k = 0; k < grid[i][j] - 1; k++) {
34 right.push([i, j]); // Ô dư đá lặp lại theo số lượng dư
35 }
36 }
37 }
38 }
39
40 return dfs(left, right);
41}
42Solution - DP & Bitmask
1function minimumMoves(grid: number[][]): number {
2 const calculateDistance = (a: [number, number], b: [number, number]): number => {
3 return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
4 };
5
6 const left: [number, number][] = [];
7 const right: [number, number][] = [];
8
9 // Xác định các ô thiếu đá (left) và dư đá (right)
10 for (let i = 0; i < 3; i++) {
11 for (let j = 0; j < 3; j++) {
12 if (grid[i][j] === 0) left.push([i, j]);
13 if (grid[i][j] > 1) {
14 for (let k = 0; k < grid[i][j] - 1; k++) {
15 right.push([i, j]); // Ô dư đá lặp lại theo số lượng dư
16 }
17 }
18 }
19 }
20
21 const n = left.length;
22 const dp = new Array(1 << n).fill(Infinity); // DP table với bitmask
23 dp[0] = 0;
24
25 // Duyệt qua tất cả các trạng thái bitmask
26 for (let mask = 0; mask < (1 << n); mask++) {
27 const count = bitCount(mask); // Số lượng ô đã được lấp đầy trong trạng thái hiện tại
28 if (count >= right.length) continue; // Nếu không còn đá dư để ghép thì bỏ qua
29
30 for (let i = 0; i < n; i++) {
31 if ((mask & (1 << i)) !== 0) continue; // Nếu ô này đã được lấp đầy thì bỏ qua
32
33 const newMask = mask | (1 << i); // Thêm ô này vào trạng thái mới
34 dp[newMask] = Math.min(
35 dp[newMask],
36 dp[mask] + calculateDistance(left[i], right[count])
37 );
38 }
39 }
40
41 return dp[(1 << n) - 1]; // Trả về chi phí tối thiểu khi tất cả các ô đã được lấp đầy
42
43 // Hàm tính số lượng bit "1" trong bitmask
44 function bitCount(mask: number): number {
45 let count = 0;
46 while (mask > 0) {
47 count += mask & 1;
48 mask >>= 1;
49 }
50 return count;
51 }
52}Time and space complexity:
| Phương pháp | Time Complexity | Space Complexity | Ưu điểm | Nhược điểm |
| Backtracking | O(n!⋅n) | O(n) | Triển khai đơn giản hơn. | Không lưu trữ trạng thái -> dễ bị tính toán lặp lại. |
| DP với Bitmask | O(2^n⋅n) | O(2^n) | Tối ưu hơn nhờ lưu trữ trạng thái -> tránh tính toán lặp lại. | Cần hiểu rõ về Bitmask và cách xây dựng bảng DP. |