Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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ài và Solution của mình trên LeetCode nhé:
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:
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 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.
Constraints:
m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j]
is 0 or 1.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:
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 0 → 0 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! 💡
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
Nguồn (nước): BFS layer 1: BFS layer 2:
⬜️ 🌊 ⬜️ 1️⃣ 🌊 1️⃣ 1️⃣ 🌊 1️⃣
🌊 ⬜️ ⬜️ → 🌊 1️⃣ ⬜️ → 🌊 1️⃣ 1️⃣
⬜️ ⬜️ ⬜️ 1️⃣ ⬜️ ⬜️ 1️⃣ 2️⃣ 2️⃣
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;
}
};
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]]
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 -1 → 0 -1 -1 ← Nước (2,0)
-1 -1 -1 -1 -1 -1
Queue ban đầu: [(0,2), (1,0)] // Các ô nước
Pop (0,2) từ queue: Pop (1,0) từ queue:
-1 -1 0 -1 1 0
-1 -1 1 → 0 -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ề
Sau vài lần pop: Trạng thái cuối:
1 1 0 1 1 0
0 1 1 → 0 1 1
1 2 2 1 2 2
Queue: [(2,1), (2,2)] Queue: rỗng (hoàn thà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️⃣
1→1→0 ✓ (chênh lệch ≤ 1)
↓ ↓ ↓
0→1→1 ✓ (chênh lệch ≤ 1)
↓ ↓ ↓
1→2→2 ✓ (chênh lệch ≤ 1)
<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>
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