909. Snakes and Ladders
Tags:
Medium
Skills:
Graph
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 tìm số lần tung xúc xác tối thiểu để đi từ ô đầu tiên đến ô cuối cùng trên bàn cờ rắn thang. Mỗi lượt, bạn có thể di chuyển từ 1 → 6 ô, và nếu đến ô có đầu rắn hoặc thang, bạn sẽ bị chuyển đến vị trí đích của rắn/ thang đó
Approach
Rắn và thang đều có chung một cơ chế: Khi bạn dừng lại ở một ô có rắn hoặc thang, bạn lập tức bị chuyển đến ô đích tương ứng (không cần tung xúc xắc thêm)
Sự khác biệt
Nhưng về mặt xử lý trong code:
board[row][col] !== -1), bạn sẽ lập tức chuyển đến ô đích đó, bất kể nó là rắn hay thang.Ví dụ:
board[row][col] = 15 (thang), bạn lập tức lên ô 15.board[row][col] = 7 (rắn), bạn lập tức tụt xuống ô 7.Trong trò chơi này, bạn chỉ bị ảnh hưởng khi dừng đúng vào “đầu” rắn hoặc “chân” thang tức là chỉ khi bạn kết thúc lượt di chuyển ở ô có số khác -1 trên bảng
Giải thích cụ thể
board[row][col] !== -1 , bạn sẽ di chuyển đến ô đích (có thể là đuôi rắn hoặc đỉnh thang)Minh họa:
Giả sử có một rắn từ ô 17 về ô 7:
Các bước chính
Solution
1function snakesAndLadders(board: number[][]): number {
2 const n = board.length;
3 function getRC(pos: number): [number, number] {
4 const row= n - 1- Math.floor((post - 1) / n);
5 let col = (pos - 1) % n;
6 if((n - 1 - row) % 2) === 1) {
7 col = n- 1 - col
8 }
9 return [row, col]
10 }
11
12 const vis: new Array(n *n + 1).fill(false)
13 const queue: [number, number][] = [[1,0]]; // [vi tri hien tai, so buoc]
14 vis[1] = true;
15 while(queue.length){
16 const [curr, moves] = queue.shift()!;
17 if(curr === n *n) return moves;
18 for(let next = curr + 1; next <= Math.min(curr + 6, n *n); next++) {
19 const [row, col] = getRC(next);
20 let dest = next;
21 if(board[row][col] !== -1) dest = board[row][col];
22 if(!vis[dest]) {
23 vis[dest] = true;
24 queue.push([dest, moves + 1]);
25 }
26 }
27 }
28 return -1;
29};const row= n - 1- Math.floor((post - 1) / n);(pos - 1)/n lấy số hàng (bắt đầu từ 0)Math.floor(...) để lấy số nguyên (vì chia lấy phần nguyên).n - 1 -... vì bàn cờ bắt đầu từ dưới lên trên (hàng cuối là 0, hàng đầu là n - 1)Tìm col let col = (pos - 1) % n
Đảo chiều cột nếu cần (zig zag)
1if ((n - 1 - row) % 2 === 1) {
2 col = n - 1 - col;
3}n - 1 - row là số thứ tự hàng tính từ dưới lên (0, 1,2,…)%2 ===1 ) thì đảo chiều cộtcol = n - 1 - col