Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

LeetCode Daily Challenge – Day 9: Minimum Cost to Make at Least One Valid Path in a Grid 🎯

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àiSolution của mình trên LeetCode nhé:

1368. Minimum Cost to Make at Least One Valid Path in a Grid

Hard
Solved 2069 Accepted

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:

  • 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
  • 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j – 1])
  • 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
  • 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i – 1][j])

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 1

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 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

Intuition

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ì:

  • Một grid m x n, mỗi ô có một mũi tên chỉ hướng
  • Xuất phát từ góc trên trái (0,0), cần đến góc dưới phải (m-1, n-1)
  • Được phép đổi hướng mũi tên, nhưng tốn chi phí 1 cho mỗi lần đổi
  • Cần tìm chi phí nhỏ nhất để có ít nhất một đường đi hợp lệ

Nghe phê chưa anh em? 😎

Quan sát quan trọng:

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)

Ví dụ phức tạp hơ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

Approach

Sau khi vò đầu bứt tai thì mình nhận ra vài điểm quan trọng:

  1. Zero-One BFS là chân ái:
   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!
  1. Quản lý hướng đi:
   - 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
  1. Deque là người anh em:
   - 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

Code Implementation

Anh em cùng xem code nè:

C++
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)
    }
};

Complexity Analysis

  • Time: O(n × m) - duyệt mỗi ô một lần, mỗi ô check 4 hướng
  • Space: O(n × m) - mảng dist và deque

Debugging Tips

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!

Kết Luận

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ớ:

  • Zero-One BFS cực kỳ hiệu quả cho bài toán có 2 loại chi phí 0-1
  • Deque giúp tối ưu thứ tự duyệt
  • Quản lý directions gọn gàng giúp code dễ đọc

CODE EDITOR

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Máy nghiền bột green life xnb4000. Pierce county features a diverse landscape with specific challenges for heavy equipment transport.