Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Daily Leetcode Challenge Day 13: 1765. Map of Highest Peak – Xây Dựng Địa Hình! 🗺️

Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ cùng nhau giải quyết một bài toán thú vị về xây dựng bản đồ độ cao! Let’s build our world! 🌎

Chào anh em, các ae có thể xem Đề bàiSolution của mình trên LeetCode nhé:

1765. Map of Highest Peak

Medium
Solved

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.

If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

  • The height of each cell must be non-negative.
  • If the cell is a water cell, its height must be 0.
  • Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)‘s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.
Example 1

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.
Example 2

Constraints:

  • m == isWater.length
  • n == isWater[i].length
  • 1 <= m, n <= 1000
  • isWater[i][j] is 0 or 1.
  • There is at least one water cell.

Problem Statement

Cho một ma trận isWater với các ô nước (1) và đất liền (0). Nhiệm vụ của chúng ta là gán độ cao cho mỗi ô sao cho:

  • Độ cao không âm
  • Ô nước có độ cao là 0
  • Độ chênh lệch giữa hai ô liền kề không quá 1
  • Maximize độ cao lớn nhất có thể

First Thoughts & Intuition

Khi mới nhìn vào bài này, mình liên tưởng ngay đến việc xây dựng một thế giới Minecraft! 🎮

Hãy cùng phân tích với ví dụ:

Ma trận nước:             Độ cao cần tìm:
0  1  0                   1  0  1
1  0  00  1  1
0  0  0                  1  2  2

Giải thích:
🌊 : Nước (độ cao = 0)
⛰️ : Đất (độ cao tăng dần từ nước)

Key Insights! 💡

  1. Bắt đầu từ nước:
   Bước 0:    Bước 1:    Bước 2:
   ?  0  ?    1  0  1    1  0  1
   0  ?  ?    0  1  ?    0  1  1
   ?  ?  ?    1  ?  ?    1  2  2
  • Nước là điểm khởi đầu cố định (độ cao = 0)
  • Lan truyền độ cao ra xung quanh như sóng
  1. BFS là perfect choice:
  • Các ô gần nước có độ cao = 1
  • Càng xa nước, độ cao càng tăng
  • BFS giúp lan truyền theo từng layer một
  1. Multi-source BFS:
   Nguồn (nước):   BFS layer 1:   BFS layer 2:
   ⬜️ 🌊 ⬜️      1️⃣ 🌊 1️⃣      1️⃣ 🌊 1️⃣
   🌊 ⬜️ ⬜️  →   🌊 1️⃣ ⬜️  →   🌊 1️⃣ 1️⃣
   ⬜️ ⬜️ ⬜️      1️⃣ ⬜️ ⬜️      1️⃣ 2️⃣ 2️⃣

Approach

  1. Khởi tạo:
  • Tạo ma trận height_map khởi tạo -1
  • Đưa tất cả ô nước vào queue với độ cao 0
  1. BFS Process:
  • Pop từng ô từ queue
  • Xét 4 hướng xung quanh
  • Gán độ cao = current + 1 cho các ô chưa visit
  1. Kết thúc:
  • Khi queue rỗng → Ta có bản đồ độ cao tối ưu!

Code Implementation

C++
class Solution {
public:
    bool isvalid(int i, int j, int m, int n, vector<vector<int>>& height_map) {
        return i >= 0 && j >= 0 && i < m && j < n && height_map[i][j] == -1;
    }

    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater[0].size();

        // Khởi tạo height_map và queue
        vector<vector<int>> height_map(m, vector<int>(n, -1));
        queue<pair<int, int>> q;

        // Đánh dấu các ô nước
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(isWater[i][j] == 1) {
                    height_map[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        // 4 hướng di chuyển
        vector<pair<int, int>> directions = {{1,0}, {0,1}, {-1,0}, {0,-1}};

        // BFS process
        while(!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for(auto [dx, dy] : directions) {
                int newX = x + dx;
                int newY = y + dy;

                if(isvalid(newX, newY, m, n, height_map)) {
                    height_map[newX][newY] = height_map[x][y] + 1;
                    q.push({newX, newY});
                }
            }
        }

        return height_map;
    }
};

Example Walkthrough

Hãy cùng phân tích chi tiết từng bước với ví dụ thú vị hơn:

Input: isWater = [[0,0,1],
                  [1,0,0],
                  [0,0,0]]

Step 1: Initialization 🌊

Ban đầu (-1 là chưa visit):     Sau khi đánh dấu nước:
-1  -1  -1                      -1  -1   0  ← Nước (1,2)
-1  -1  -10   -1  -1  ← Nước (2,0)
-1  -1  -1                      -1  -1  -1

Queue ban đầu: [(0,2), (1,0)]  // Các ô nước

Step 2: First BFS Wave 🌊 → 🏔️

Pop (0,2) từ queue:             Pop (1,0) từ queue:
-1  -1   0                      -1   1   0
-1  -1   10   -1   1
-1  -1  -1                      1   -1  -1

Queue: [(1,0), (1,2)]          Queue: [(0,1), (1,1), (2,0), (1,2)]
Giải thích: Các ô cạnh nước    Giải thích: Tiếp tục lan rộng với
được gán độ cao 1              độ cao 1 cho các ô kề

Step 3: Second BFS Wave 🏔️ → ⛰️

Sau vài lần pop:               Trạng thái cuối:
1    1    0                    1    1    0
0    1    10    1    1
1    2    2                   1    2    2

Queue: [(2,1), (2,2)]         Queue: rỗng (hoàn thành!)

Animation của quá trình:

Step 0:    Step 1:    Step 2:    Final:
⬜️⬜️🌊    ⬜️⬜️🌊    1️⃣1️⃣🌊    1️⃣1️⃣🌊
🌊⬜️⬜️ →  🌊1️⃣1️⃣ →  🌊1️⃣1️⃣ →  🌊1️⃣1️⃣
⬜️⬜️⬜️    1️⃣⬜️⬜️    1️⃣2️⃣2️⃣    1️⃣2️⃣2️⃣

Verification của kết quả:

  1. Độ cao hợp lệ?
  • Tất cả đều không âm
  • Ô nước có độ cao 0
  1. Chênh lệch giữa các ô?
   110  ✓ (chênh lệch ≤ 1)
   ↓ ↓ ↓
   011  ✓ (chênh lệch ≤ 1)
   ↓ ↓ ↓
   122  ✓ (chênh lệch ≤ 1)
  1. Maximum height tối ưu?
  • Độ cao max = 2
  • Không thể cao hơn do bị giới hạn bởi các ô nước

Pro Tips từ ví dụ:

  1. BFS lan truyền theo layer giúp tự động thỏa mãn điều kiện chênh lệch ≤ 1
  2. Độ cao maximum sẽ xuất hiện ở các ô xa nước nhất
  3. Có thể có nhiều cách gán độ cao khác nhau cùng thỏa mãn yêu cầu
<em>Ví dụ này cho thấy sức mạnh của BFS trong việc lan truyền theo layer và tự động tối ưu độ cao! 🚀</em>

Complexity Analysis

  • Time: O(m * n) - mỗi ô được visit một lần
  • Space: O(m * n) - cho queue và height_map

Tips & Tricks

  1. Multi-source BFS là key cho bài này
  2. Đừng quên check valid trước khi thêm vào queue
  3. Dùng directions array để code clean hơn

Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀

P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨

CODE EDITOR

#leetcode #leetcodedaily #algorithms #programming #learningwithlosers

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?
Choose logi transports for your heavy equipment transport needs in new york, ny.