Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

Daily Leetcode Challenge Day 19: 2658. Maximum Number of Fish in a Grid – Hành Trình Câu Cá! 🎣

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

2658. Maximum Number of Fish in a Grid

Medium
Đã giải

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:

  • Một ô đất nếu grid[r][c] = 0, hoặc
  • Một ô nước chứa grid[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:

  • Bắt tất cả cá trong ô (r, c), hoặc
  • Di chuyển đến bất kỳ ô nước liền kề nào.

Trả 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 1

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á.
Example 2

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • 0 <= grid[i][j] <= 10

First Thoughts & Intuition 🧠

Khi nhìn vào bài này, mình liên tưởng đến một trò chơi câu cá:

1. Phân tích Bản đồ 🗺️

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

2. Tư Duy DFS 🎯

  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

3. Visualization của Connected Components 🌊

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)

Super Detailed Approach 📝

1. DFS Implementation 🚀

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

2. Full Solution 🎨

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

Example Walkthrough 🎮

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)

Visual Insights 🎨

Chiến lược DFS:       Pattern nhận dạng:
🌊→🌊→🌊             Connected:    Disconnected:
↓  ↓  ↓              🌊🌊🌊       🌊⬛🌊
🌊→🌊→🌊             🌊🌊🌊       ⬛⬛⬛
                     🌊🌊🌊       🌊⬛🌊

Complexity Analysis 📊

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

Tips & Tricks 💡

  1. Optimization Tips:
- Use vector for directions
- Early termination if found max possible
- Cache visited cells
  1. Edge Cases:
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
  1. Debugging Tips:
- 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

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?
Cdl scholarship logi transports fast & reliable heavy equipment transport & transport services.