leetcode

commit cf327982d05967334ca414492d16b3e4ec7ea9f2
parent 11378f5654c0d05bd9d97404a6e0e13671ce4758
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 23 Nov 2023 19:30:44 +0000

1 Random Problem

Diffstat:
A
Problems/2658.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/Problems/2658.cpp b/Problems/2658.cpp
@@ -0,0 +1,34 @@
+class Solution {
+  public:
+    int findMaxFish(vector<vector<int>> &grid) const {
+        static const int offset[] = {1, 0, -1, 0, 1};
+        const int n = grid.size(), m = grid[0].size();
+        const auto valid = [n, m](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
+        int res = 0;
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++) {
+                if (!grid[i][j]) continue;
+                int count = grid[i][j];
+                grid[i][j] = 0;
+
+                queue<pair<int, int>> q;
+                q.push({i, j});
+                while (!q.empty()) {
+                    const auto [a, b] = q.front();
+                    for (int k = 0; k < 4; k++) {
+                        const int x = a + offset[k];
+                        const int y = b + offset[k + 1];
+                        if (!valid(x, y)) continue;
+                        if (!grid[x][y]) continue;
+                        count += grid[x][y];
+                        grid[x][y] = 0;
+                        q.push({x, y});
+                    }
+                    q.pop();
+                }
+                res = max(res, count);
+            }
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -896,6 +896,7 @@ for solving problems.
 |  2641  |   Medium   | [Cousins in Binary Tree II](Problems/2641.cpp)                                                     |
 |  2642  |    Hard    | [Design Graph With Shortest Path Calculator](Problems/2642.cpp)                                    |
 |  2657  |   Medium   | [Find the Prefix Common Array of Two Arrays](Problems/2657.cpp)                                    |
+|  2658  |   Medium   | [Maximum Number of Fish in a Grid](Problems/2658.cpp)                                              |
 |  2665  |    Easy    | [Counter II](Problems/2665.js)                                                                     |
 |  2666  |    Easy    | [Allow One Function Call](Problems/2666.js)                                                        |
 |  2667  |    Easy    | [Create Hello World Function](Problems/2667.js)                                                    |