Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào anh em đồng môn coder! Sau một chuỗi ngày vật lộn với các bài medium và bitwise operation, hôm nay LeetCode đã “chiêu đãi” chúng ta một bài hard đầu tiên trong chuỗi daily challenge! Let’s dive deep vào bài này nào! 🚀
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:
Notice that there could be some signs on the cells of the grid that point outside the grid.
You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m – 1, n – 1) following the signs on the grid. The valid path does not have to be the shortest.
You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.
Return the minimum cost to make the grid have at least one valid path.
Example 1:
Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] Output: 3 Explanation: You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3) The total cost = 3.
Example 2:
Input: grid = [[1,1,3],[3,2,2],[1,1,4]] Output: 0 Explanation: You can follow the path from (0, 0) to (2, 2).
Example 3:
Input: grid = [[1,2],[4,3]] Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 4
Happy coding anh em nhé! 🎉👨💻
Chào anh em! Đối với một bài hard đầu tiên, việc đọc hiểu đề bài cực kỳ quan trọng. Chúng ta có gì:
Nghe phê chưa anh em? 😎
Input: grid = [[1,1,1,1],
[2,2,2,2],
[1,1,1,1],
[2,2,2,2]]
Ví dụ minh họa đường đi:
(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3) -> (3,3)
Chi phí = 0 vì:
- (0,0): mũi tên phải (1) -> đi phải ✓
- (0,1): mũi tên phải (1) -> đi phải ✓
- (0,2): mũi tên phải (1) -> đi phải ✓
- (0,3): mũi tên phải (1) -> đi xuống (cần đổi, +1)
- (1,3): mũi tên xuống (2) -> đi xuống ✓
- (2,3): mũi tên xuống (2) -> đi xuống ✓
- (3,3): đích đến ✓
Tổng chi phí: 1 (chỉ cần đổi 1 mũi tên)
Input: grid = [[1,1,3],
[3,2,2],
[1,1,4]]
Các đường đi có thể:
1) (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
Chi phí = 2 (đổi hướng ở (0,2) và (1,2))
2) (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2)
Chi phí = 3 (đổi hướng ở (0,1), (1,1), và (1,2))
-> Minimum cost = 2
Sau khi vò đầu bứt tai thì mình nhận ra vài điểm quan trọng:
Tuy có thể sử dụng dijkstra nhưng việtc sài deque thay vì priority queue sẽ tối ưu hơn do trọng số của graph khi ta mô hình hóa bài toán chỉ có 0 hoặc 1.<br> - Đi theo mũi tên: chi phí 0<br> - Đổi hướng mũi tên: chi phí 1<br> -> Hoàn hảo cho Zero-One BFS!
- 4 hướng cơ bản: phải, trái, xuống, lên
- Dùng mảng directions để quản lý cho gọn
- Không tốn chi phí: thêm vào đầu
- Tốn chi phí 1: thêm vào cuối
-> Đảm bảo tối ưu thứ tự duyệt
Anh em cùng xem code nè:
class Solution {
public:
vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool is_valid(int i, int j, int n, int m) {
return i >= 0 && j >= 0 && i < n && j < m;
}
int minCost(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
// Khởi tạo khoảng cách ban đầu là vô cực
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
deque<pair<int, int>> dq; // Hàng đợi 0-1 BFS
// Bắt đầu từ ô (0, 0)
dist[0][0] = 0;
dq.push_front({0, 0});
while (!dq.empty()) {
auto [i, j] = dq.front();
dq.pop_front();
// Duyệt 4 hướng
for (int d = 0; d < 4; d++) {
int ni = i + directions[d][0];
int nj = j + directions[d][1];
if (is_valid(ni, nj, n, m)) {
// Trọng số của cạnh
int cost = (grid[i][j] == d + 1) ? 0 : 1;
// Nếu tìm được đường đi ngắn hơn
if (dist[i][j] + cost < dist[ni][nj]) {
dist[ni][nj] = dist[i][j] + cost;
if (cost == 0) {
dq.push_front({ni, nj}); // Thêm vào đầu hàng đợi nếu trọng số = 0
} else {
dq.push_back({ni, nj}); // Thêm vào cuối hàng đợi nếu trọng số = 1
}
}
}
}
}
return dist[n - 1][m - 1]; // Khoảng cách đến ô (n-1, m-1)
}
};
Một số lỗi thường gặp khi implement:
1. Quên check biên:
if (is_valid(ni, nj, n, m)) là crucial!
2. Sai thứ tự push vào deque:
- cost = 0: push_front
- cost = 1: push_back
Đảo lộn thứ tự -> WA!
3. Không reset dist array:
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
Quan trọng để tránh cycle!
Bài này tuy hard nhưng với Zero-One BFS thì cũng không quá khó phải không anh em? Key points cần nhớ:
CODE EDITOR