문제는 그리드의 물 세포에서 시작하여 피셔가 잡을 수있는 최대 물고기 수를 찾는 것입니다. 피셔는 현재 세포에서 물고기를 잡아서 인접한 물 세포 (위, 아래, 왼쪽 또는 오른쪽)로 이동할 수 있습니다.
핵심 사항 :
그리드에는 토지 (값 0) 또는 물 (값 & gt; 0) 인 셀이 포함되어 있습니다.
피셔는 인접한 물 세포로만 이동할 수 있습니다
목표는 가능한 최상의 수위에서 시작하여 수집 가능한 최대 수의 수를 찾는 것입니다.
-
접근하다:
-
- 각 수 세포에서 시작하여 가능한 모든 경로를 탐색하려면 깊이 우선 검색 (dfs) 를 탐색하십시오.
방문되지 않은 각 물 세포의 경우 연결된 구성 요소의 총 물고기를 계산하기 위해 DFS를 실행하십시오.
연결된 구성 요소에서 수집 한 최대 물고기를 추적합니다
계획:
셀이 탐색되었는지 여부를 추적하기 위해 2D 방문 배열을 초기화합니다.
그리드의 각 셀을 통해 반복
셀에 물이 들어 있고 방문하지 않은 경우 :
-
해당 셀에서 시작하여 DFS를 실행하십시오
연결된 물 세포의 총 물고기를 축적하십시오
지금까지 수집 한 최대 물고기를 업데이트하십시오
모든 세포를 탐색 한 후 최대 물고기 수를 반환하십시오
PHP 에서이 솔루션을 구현합시다 : - 2658. 그리드의 최대 물고기 수
-
설명:
DFS 구현 :
-
각 수 세포 (R, C)에 대해 이웃을 재귀 적으로 탐색하면 다음과 같습니다.
-
그리드 경계 내부
<.> 참조
물 세포 (값 & gt; 0).
-
재귀 중에 어류 수를 축적합니다
-
단계 :
-
수 세포에서 시작하여 방문한대로 표시하십시오.
재귀 적으로 유효한 이웃을 방문하여 물고기 수를 추가합니다.
연결된 구성 요소의 총 물고기 수를 반환합니다
-
예제 연습 :
예제 입력 :
-
|
실행:
(1, 3)에서 시작하십시오 (value = 3). DFS 실행 :
(1, 3) → (2, 3) (value = 4)
총 물고기 = 3 4 = 7.
<?php
/**
* @param Integer[][] $grid
* @return Integer
*/
function findMaxFish($grid) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Helper function for DFS
* @param $r
* @param $c
* @param $grid
* @param $visited
* @param $rows
* @param $cols
* @param $directions
* @return array|bool|int|int[]|mixed|null
*/
function dfs($r, $c, &$grid, &$visited, $rows, $cols, $directions) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example 1
grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]];
echo getMaxFish($grid); // Output: 7
// Example 2
$grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]];
echo getMaxFish($grid); // Output: 1
?>
다른 물 세포를 탐색하지만 연결된 구성 요소는 총 물고기 수가 더 높지 않습니다.
출력 : 7.
시간 복잡성 :
-
각 셀이 한 번 방문됩니다 → O (m × n).
-
<:> 전반적인 복잡성 :
-
예제의 출력 :
-
예 1 :
7
예제 2 : 1
솔루션은 DFS를 효율적으로 사용하여 물 세포의 연결된 구성 요소를 탐색하고 모든 물 세포에서 시작하는 어부가 잡을 수있는 최대 물고기를 계산합니다. 이 접근법은 최적의 탐사를 보장하고 주어진 제약 조건에 잘 어울립니다.
연락처 링크 - 이 시리즈가 도움이된다면 리포지토리 Github에 별을 주거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다!
이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 :
LinkedIn
github
