Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!
Ngày mùng 3 Tết Ất Tỵ 2025, chúng ta lại cùng nhau chinh phục một bài toán Hard cực kỳ thú vị – Making A Large Island! Hãy tưởng tượng bạn là một “kiến trúc sư đảo” với khả năng biến nước thành đất! Cùng bắt đầu hành trình khám phá nhé! 🚀
Bạn được cung cấp một ma trận nhị phân grid
có kích thước n x n
. Bạn được phép thay đổi tối đa một giá trị từ 0
thành 1
.
Trả về kích thước của hòn đảo lớn nhất trong grid
sau khi thực hiện thao tác này.
Một “hòn đảo” là một nhóm các số 1
liên kết với nhau theo 4 hướng (trên, dưới, trái, phải).
Example 1:
Input: grid = [[1,0],[0,1]] Output: 3 Explanation: Thay đổi một số 0 thành 1 và kết nối hai số 1, sau đó ta sẽ có một hòn đảo với diện tích = 3.
Example 2:
Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Thay đổi số 0 thành 1 và làm cho hòn đảo lớn hơn, chỉ còn một hòn đảo với diện tích = 4.
Example 3:
Input: grid = [[1,1],[1,1]] Output: 4 Explanation: Không thể thay đổi bất kỳ số 0 nào thành 1, chỉ có một hòn đảo với diện tích = 4.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j]
chỉ có giá trị là 0
hoặc 1
.Bạn được cho một ma trận nhị phân n x n (grid). Nhiệm vụ của bạn là:
Khi nhìn vào bài toán này, chúng ta có thể thấy một số pattern thú vị:
Trường hợp 1: Các đảo riêng lẻ
🌳🌳🌊
🌊🌊🌳
🌳🌳🌊
Nhận xét: Hai đảo riêng biệt đang chờ được kết nối! Chúng ta cần tìm điểm kết nối tối ưu để tạo ra đảo lớn nhất.
Trường hợp 2: Đảo đã kết nối một phần
🌳🌳🌊
🌳🌊🌳
🌊🌊🌳
Nhận xét: Một đảo lớn và một đảo nhỏ – cần một cây cầu kết nối thông minh!
Trước tiên, chúng ta cần một hệ thống để nhận diện và đánh dấu các đảo riêng biệt:
Bước 1: Đánh dấu các đảo
Before: Ma trận ban đầu
🌳🌳🌊
🌊🌊🌳
🌳🌳🌊
After: Sau khi đánh dấu
2️⃣2️⃣🌊
🌊🌊3️⃣
4️⃣4️⃣🌊
Mỗi đảo được đánh dấu bằng một ID riêng (2, 3, 4…) để dễ dàng theo dõi và tính toán.
Chúng ta cần một hệ thống theo dõi kích thước của từng đảo:
Island Registry 📋:
Khi xem xét một ô nước (0), chúng ta cần:
Direction Check:
⬆️ Phía Trên: Kiểm tra Island ID
⬅️ Bên Trái: Kiểm tra Island ID
➡️ Bên Phải: Kiểm tra Island ID
⬇️ Phía Dưới: Kiểm tra Island ID
Size Calculation:
Kích thước mới = 1 (ô được biến đổi) + Tổng kích thước các đảo xung quanh
class Solution {
public:
// Possible directions for movement: right, left, down, and up
vector<pair<int,int>> direct = {{0,1},{0,-1},{1,0},{-1,0}};
// Function to check if a given position (i, j) is within grid bounds
bool is_valid(int i, int j, vector<vector<int>>& grid) {
return (i >= 0) && (j >= 0) && (i < grid.size()) && (j < grid[0].size());
}
// Depth-First Search (DFS) to mark and count the size of an island
void dfs(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& visited, int &curk, int &cnt) {
visited[i][j] = true; // Mark the cell as visited
grid[i][j] = curk; // Assign a unique island identifier
cnt += 1; // Increase the island size counter
// Explore all four possible directions
for(auto it : direct) {
int newdx = i + it.first;
int newdy = j + it.second;
// If the new position is valid, unvisited, and part of an island (grid value = 1), continue DFS
if (is_valid(newdx, newdy, grid) && !visited[newdx][newdy] && grid[newdx][newdy] == 1) {
dfs(newdx, newdy, grid, visited, curk, cnt);
}
}
}
int largestIsland(vector<vector<int>>& grid) {
int curk = 2; // Unique identifier for each island, starting from 2 (since 1 represents land)
int cnt_max = 0; // Variable to store the size of the largest island
map<int, int> marked_cnt_each_island; // Stores the size of each uniquely marked island
// Create a visited grid initialized to false
vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), false));
// Step 1: Identify and mark all islands with unique identifiers using DFS
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
int cnt = 0; // Counter for the current island's size
// If the current cell is land (1) and has not been visited, start DFS
if (!visited[i][j] && grid[i][j] == 1) {
dfs(i, j, grid, visited, curk, cnt);
marked_cnt_each_island[curk] = cnt; // Store the size of this island
cnt_max = max(cnt_max, cnt); // Update the max island size
curk++; // Increment island identifier for the next island
}
}
}
// Edge case 1: If the entire grid is an island (no zeros), return its size
if (cnt_max == grid.size() * grid[0].size()) {
return cnt_max;
}
// Edge case 2: If there are no islands, flipping one cell to land gives size 1
else if (cnt_max == 0) {
return 1;
}
// Step 2: Try converting each water cell (0) into land (1) to form a larger island
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 0) {
int cnt = 1; // Start with size 1 (this flipped cell)
set<int> unique_islands; // To avoid counting the same island twice
// Check all four directions to find adjacent islands
for (auto it : direct) {
int newdx = i + it.first;
int newdy = j + it.second;
// If valid, add the island identifier to the set
if (is_valid(newdx, newdy, grid)) {
unique_islands.insert(grid[newdx][newdy]);
}
}
// Sum the sizes of unique neighboring islands
for (auto it : unique_islands) {
cnt += marked_cnt_each_island[it];
}
// Update the maximum possible island size
cnt_max = max(cnt, cnt_max);
}
}
}
return cnt_max; // Return the largest possible island size
}
};
Hãy phân tích một ví dụ cụ thể:
Input Grid:
🌳🌳🌊
🌳🌊🌳
🌊🌊🌳
Step 1: Label Islands
2️⃣2️⃣🌊
2️⃣🌊3️⃣
🌊🌊3️⃣
Step 2: Size Tracking
Step 3: Find Best Transform
Point (1,1) kết nối cả hai đảo:
2️⃣2️⃣🌊
2️⃣✨3️⃣
🌊🌊3️⃣
Final Result: 6 ô (3 + 2 + 1)
Step 1: Mark Islands
⬛⬛⬜ Islands được mark với các ID khác nhau để dễ track!
⬛⬜🟦
⬜🟦🟦
Step 2: Find Bridges
⬛⬛❓ Các điểm có thể transform được đánh dấu bằng ❓
⬛❓🟦
❓🟦🟦
Step 3: Calculate
⬛⬛✨ Chọn điểm transform tối ưu nhất để maximize size!
⬛❓🟦
❓🟦🟦
Good Transform Points:
⬛❓🟦 → High impact! Connects many islands!
❓⬛🟦
🟦🟦⬛
Bad Transform Points:
⬛⬛❓ → Low impact! Only connects few cells!
⬛⬛⬛
❓⬛⬛
Early Exit Cases:
🌳🌳🌳
🌳🌳🌳 → All land? Return n*n, no need to check!
🌳🌳🌳
🌊🌊🌊
🌊🌊🌊 → All water? Return 1, just one cell!
🌊🌊🌊
Time Complexity: O(N²)
Space Complexity: O(N²)
Bài toán này là một ví dụ tuyệt vời về việc kết hợp:
Chúc mừng năm mới 2025! Hãy 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 #dailycoding #graphs #dfs #LearningWithLosers #newyear2025 #tetholidaycoding