그리드의 최대 물고기 수

<.> 2658. 그리드의 최대 물고기 수

난이도 :

중간 주제 :

배열, 깊이 우선 검색, 폭이 넓은 검색, Union Find, Matrix 당신은 크기 m x n 크기의 2d 행렬 그리드가 주어지며, 여기서 (r, c)는 다음을 나타냅니다. land land

셀 인 경우 [r] [c] = 0 또는 그리드 [r] [c] 물고기를 함유하는 셀 셀 물 셀, 그리드 [r] [c] & gt; 0.

피셔는 물

셀 (R, C)에서 시작할 수 있으며 다음 작업을 여러 번 수행 할 수 있습니다. 세포에서 모든 물고기를 잡아 (r, c) 또는 인접한 물

셀로 이동

• return 최대 물고기의 수는 피셔가 시작 세포를 최적으로 선택할 때 잡을 수 있거나, 물 세포가 없으면 0 .
an 인접한
• 세포 (r, c)는 세포 중 하나 (r, c 1), (r, c -1), (r 1, c) 또는 (r -1, c) 존재하는 경우 예 1 :

입력 : grid = [[0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0] ] 출력 : 7 <:> 설명 :

피셔는 세포 (1,3)에서 시작하여 3 마리의 물고기를 모은 다음 세포 (2,3)로 이동하여 4 개의 물고기를 모을 수 있습니다.

• 예제 2 :
입력 : grid = [[1,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,1] ]

출력 :

1 <:> 설명 : 피셔는 세포 (0,0) 또는 (3,3)에서 시작하여 단일 물고기를 모을 수 있습니다. 제약 조건 :

m == grid.length n == 그리드 [i] .length

1 & lt; = m, n & lt; = 10 0 & lt; = 그리드 [i] [j] & lt; = 10

힌트 :

0이 아닌 각각의 셀에서 dfs를 실행하십시오 시작하기 위해 세포를 선택할 때마다 방문하는 세포에 포함 된 물고기의 수를 추가하십시오. 솔루션 :

문제는 그리드의 물 세포에서 시작하여 피셔가 잡을 수있는 최대 물고기 수를 찾는 것입니다. 피셔는 현재 세포에서 물고기를 잡아서 인접한 물 세포 (위, 아래, 왼쪽 또는 오른쪽)로 이동할 수 있습니다.

핵심 사항 :

그리드에는 토지 (값 0) 또는 물 (값 & gt; 0) 인 셀이 포함되어 있습니다. 피셔는 인접한 물 세포로만 이동할 수 있습니다 목표는 가능한 최상의 수위에서 시작하여 수집 가능한 최대 수의 수를 찾는 것입니다.
접근하다:
3. 각 수 세포에서 시작하여 가능한 모든 경로를 탐색하려면 깊이 우선 검색 (dfs) 를 탐색하십시오. 방문되지 않은 각 물 세포의 경우 연결된 구성 요소의 총 물고기를 계산하기 위해 DFS를 실행하십시오. 연결된 구성 요소에서 수집 한 최대 물고기를 추적합니다

계획:

셀이 탐색되었는지 여부를 추적하기 위해 2D 방문 배열을 초기화합니다. 그리드의 각 셀을 통해 반복 셀에 물이 들어 있고 방문하지 않은 경우 :
1. 해당 셀에서 시작하여 DFS를 실행하십시오 연결된 물 세포의 총 물고기를 축적하십시오 지금까지 수집 한 최대 물고기를 업데이트하십시오 모든 세포를 탐색 한 후 최대 물고기 수를 반환하십시오
PHP 에서이 솔루션을 구현합시다 :
2. 2658. 그리드의 최대 물고기 수

설명:

DFS 구현 :
각 수 세포 (R, C)에 대해 이웃을 재귀 적으로 탐색하면 다음과 같습니다.
2. 그리드 경계 내부 <.> 참조 물 세포 (값 & gt; 0).
3. 재귀 중에 어류 수를 축적합니다
   • 단계 :
   • 수 세포에서 시작하여 방문한대로 표시하십시오.
   재귀 적으로 유효한 이웃을 방문하여 물고기 수를 추가합니다. 연결된 구성 요소의 총 물고기 수를 반환합니다
   예제 연습 :
예제 입력 :

실행:

(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를 효율적으로 사용하여 물 세포의 연결된 구성 요소를 탐색하고 모든 물 세포에서 시작하는 어부가 잡을 수있는 최대 물고기를 계산합니다. 이 접근법은 최적의 탐사를 보장하고 주어진 제약 조건에 잘 어울립니다.

연락처 링크
1. 이 시리즈가 도움이된다면 리포지토리 Github에 별을 주거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다!

   이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 : LinkedIn

   github

위 내용은 그리드의 최대 물고기 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!