→ deatheo: 大師 01/28 14:58
推 Furina: 大師 01/28 15:12
https://leetcode.com/problems/maximum-number-of-fish-in-a-grid
2658. Maximum Number of Fish in a Grid
給你一個二維陣列 grid 表示矩陣，grid[r][c] = 0 表示陸地，否則為水
，數字表示水裡有幾隻魚，你可以挑一個水池入水，然後抓完那個水池的所有魚，
如果有相鄰池子的話你可以遊過去繼續抓，求出最多可以抓多少魚。
思路:
1.用dfs遍歷所有單元格，找到最大的可抓魚數量，走過的格子標記避免重複走訪，
要省空間就直接把走過的格子設定為0就好。
java code
---------------------------------------------------
class Solution {
private boolean[][] visited;
private int[][] grid;
private int m;
private int n;
public int findMaxFish(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
this.visited = new boolean[m][n];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int fishes = dfs(i, j);
res = Math.max(res, fishes);
}
}
return res;
}
int dfs(int y, int x) {
if (y < 0 || y >= m || x < 0 || x >= n
|| visited[y][x] || grid[y][x] == 0) {
return 0;
}
visited[y][x] = true;
return grid[y][x] + dfs(y + 1, x) + dfs(y - 1, x)
+ dfs(y, x + 1) + dfs(y, x - 1);
}
}
---------------------------------------------------
--
https://i.imgur.com/SLF19AR.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738046754.A.A73.html
※ 編輯: Rushia (49.158.101.161 臺灣), 01/28/2025 14:47:49