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 Loser1! Hôm nay chúng ta sẽ cùng nhau giải quyết một bài toán thú vị về việc câu cá trên một ma trận 2D. Let’s go fishing! 🌊
Bạn được cung cấp một ma trận 2D có kích thước m x n
, trong đó (r, c)
đại diện cho:
grid[r][c] = 0
, hoặcgrid[r][c]
con cá, nếu grid[r][c] > 0
.Một ngư dân có thể bắt đầu từ bất kỳ ô nước nào (r, c)
và có thể thực hiện các thao tác sau bất kỳ số lần nào:
(r, c)
, hoặcTrả về số lượng cá tối đa mà ngư dân có thể bắt được nếu chọn ô bắt đầu một cách tối ưu, hoặc 0
nếu không có ô nước nào tồn tại.
Một ô liền kề của ô (r, c)
là một trong các ô (r, c + 1)
, (r, c - 1)
, (r + 1, c)
hoặc (r - 1, c)
nếu nó tồn tại.
Example 1:
Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]] Output: 7 Explanation: Ngư dân có thể bắt đầu từ ô (1,3) và bắt được 3 con cá, sau đó di chuyển đến ô (2,3) và bắt được 4 con cá.
Example 2:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] Output: 1 Explanation: Ngư dân có thể bắt đầu từ ô (0,0) hoặc (3,3) và bắt được một con cá.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10
Khi nhìn vào bài này, mình liên tưởng đến một trò chơi câu cá:
Input grid:
0 2 1 0 Trong đó:
4 0 0 3 🌊 Water cell (>0): Có cá
1 0 0 4 ⬛ Land cell (=0): Đất liền
0 3 2 0
Ví dụ tại (1,3):
↑
← 3 → Từ một ô, ta có thể:
↓ 1. Bắt tất cả cá tại ô đó
2. Di chuyển sang ô kề có nước
Nhóm cá 1: Nhóm cá 2:
0 2 1 0 0 🐟 🐟 0
4 0 0 3 🐟 0 0 🐟
1 0 0 4 🐟 0 0 🐟
0 3 2 0 0 🐟 🐟 0
Total: 7 fish (Các ô có nước kề nhau)
void dfs(int r, int c, vector<vector<int>>& grid,
vector<vector<bool>>& visited, int& fish_count) {
// Đánh dấu đã thăm và cộng số cá
visited[r][c] = true;
fish_count += grid[r][c];
// Các hướng di chuyển: phải, trái, lên, xuống
vector<pair<int,int>> directions = {
{0,1}, {0,-1}, {1,0}, {-1,0}
};
// Duyệt các ô kề
for(auto [dr, dc] : directions) {
int new_r = r + dr;
int new_c = c + dc;
// Kiểm tra điều kiện và đệ quy
if(isValid(new_r, new_c, grid, visited)) {
dfs(new_r, new_c, grid, visited, fish_count);
}
}
}
class Solution {
public:
bool isValid(int r, int c, vector<vector<int>>& grid,
vector<vector<bool>>& visited) {
return r >= 0 && r < grid.size() &&
c >= 0 && c < grid[0].size() &&
grid[r][c] > 0 && !visited[r][c];
}
int findMaxFish(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
int max_fish = 0;
// Duyệt toàn bộ grid
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(!visited[i][j] && grid[i][j] > 0) {
int current_fish = 0;
dfs(i, j, grid, visited, current_fish);
max_fish = max(max_fish, current_fish);
}
}
}
return max_fish;
}
};
Input: grid = [[0,2,1,0],
[4,0,0,3],
[1,0,0,4],
[0,3,2,0]]
Step 1: Start từ (1,3) có số cá = 3
Current: 3 fish
⬛🐟🐟⬛
🐟⬛⬛🎣
🐟⬛⬛🐟
⬛🐟🐟⬛
Step 2: Di chuyển xuống (2,3) có số cá = 4
Current: 7 fish
⬛🐟🐟⬛
🐟⬛⬛✓
🐟⬛⬛🎣
⬛🐟🐟⬛
Final Result: 7 fish (maximum possible)
Chiến lược DFS: Pattern nhận dạng:
🌊→🌊→🌊 Connected: Disconnected:
↓ ↓ ↓ 🌊🌊🌊 🌊⬛🌊
🌊→🌊→🌊 🌊🌊🌊 ⬛⬛⬛
🌊🌊🌊 🌊⬛🌊
Time: O(m * n)
└── Duyệt qua mỗi ô một lần
└── DFS không visit lại ô đã thăm
Space: O(m * n)
└── Visited array
└── Recursion stack
- Use vector for directions
- Early termination if found max possible
- Cache visited cells
Case 1: All land
[[0,0],
[0,0]] → Return 0
Case 2: Single water cell
[[0,1],
[0,0]] → Return 1
Case 3: Multiple components
[[1,0,1],
[0,0,0],
[1,0,1]] → Check all
- Print visited cells
- Track current fish count
- Visualize connected components
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é! 💻✨
#leetcode #leetcodedaily #algorithms #programming #learningwithlosers
CODE EDITOR