Nombre maximum de poissons dans une grille

2658. Nombre maximum de poissons dans une grille

Difficulté: moyen

Sujets: tableau, recherche en profondeur d'abord, largeur de recherche, un syndicat, matrice

On vous donne une grille matricielle 0 indexée 2D de taille m x n, où (r, c) représente:

• a Land Cell Si la grille [r] [c] = 0, ou
• a water Cell contenant la grille [r] [c] poisson, si la grille [r] [c] & gt; 0.

Un pêcheur peut commencer à n'importe quelle cellule eau (r, c) et peut effectuer les opérations suivantes un certain nombre de fois:

• attraper tous les poissons à la cellule (r, c), ou
• Déplacez-vous vers n'importe quelle cellule adjacente eau .

retour le maximum nombre de poissons que Fisher peut attraper s'il choisit sa cellule de départ de manière optimale, ou 0 si aucune cellule d'eau n'existe .

une cellule adjacente adjacente de la cellule (R, C), est l'une des cellules (R, C 1), (R, C - 1), (R 1, C) ou (R - 1, c) s'il existe.

Exemple 1:

• Entrée: grid = [[0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0] ]
• Sortie: 7
• Explication: Le Fisher peut commencer à la cellule (1,3) et collecter 3 poissons, puis se déplacer vers la cellule (2,3) et collecter 4 poissons.

Exemple 2:

• Entrée: grid = [[1,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,1] ]
• Sortie: 1
• Explication: Le pêcheur peut commencer par les cellules (0,0) ou (3,3) et collecter un seul poisson.

Contraintes:

m == grid.length
n == grid [i] .length
1 & lt; = m, n & lt; = 10
0 & lt; = grid [i] [j] & lt; = 10

Indice:

Exécutez des DF à partir de chaque cellule non nulle.
Chaque fois que vous choisissez une cellule pour commencer, additionnez le nombre de poissons contenus dans les cellules que vous visitez.

Solution:

Le problème est de trouver le nombre maximum de poissons qu'un Fisher peut attraper en commençant à n'importe quelle cellule d'eau dans une grille. Le Fisher peut attraper des poissons à la cellule actuelle et se déplacer vers n'importe quelle cellule d'eau adjacente (en haut, en bas, à gauche ou à droite) à plusieurs reprises.

Points clés:

1. La grille contient des cellules qui sont soit des terres (valeur 0) ou de l'eau (valeur & gt; 0).
2. Le Fisher ne peut se déplacer que vers les cellules d'eau adjacentes.
3. L'objectif est de trouver le nombre maximum de poissons collectables, à partir de la meilleure cellule d'eau possible.

Approche:

1. Utiliser Recherche en profondeur-première (DFS) pour explorer tous les chemins possibles à partir de chaque cellule d'eau.
2. Pour chaque cellule d'eau non visitée, exécutez un DFS pour calculer le poisson total dans le composant connecté.
3. Suivez le poisson maximum collecté à partir de tout composant connecté.

Plan:

1. Initialiser un tableau visité 2D pour expliquer si une cellule a été explorée.
2. itérater à travers chaque cellule de la grille.
3. Si la cellule contient de l'eau et n'est pas visitée:
   • Exécutez un DFS à partir de cette cellule.
   • accumuler le poisson total dans les cellules d'eau connectées.
   • Mettez à jour les poissons maximaux collectés jusqu'à présent.
4. Renvoyez le nombre maximal de poissons après avoir exploré toutes les cellules.

Implémentons cette solution dans PHP: 2658. Nombre maximum de poissons dans une grille

<?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
?>

Explication:

Implémentation DFS:

• Pour chaque cellule à eau (R, C), explorez récursivement ses voisins s'ils sont:
  • à l'intérieur des limites de la grille.
  • non visité.
  • cellules d'eau (valeur & gt; 0).
• accumuler le nombre de poissons pendant la récursivité.

Mesures:

1. Commencez à partir d'une cellule à eau et marquez-la comme visité.
2. visitez récursivement ses voisins valides, additionnant le nombre de poissons.
3. Renvoyez le nombre total de poissons pour le composant connecté.

Exemple de procédure pas à pas:

Exemple d'entrée:

$grid = [
    [0, 2, 1, 0],
    [4, 0, 0, 3],
    [1, 0, 0, 4],
    [0, 3, 2, 0]
];

Exécution:

1. Commencer à (1, 3) (valeur = 3). Exécutez DFS:
   • (1, 3) → (2, 3) (valeur = 4).
   • Fish total = 3 4 = 7.
2. Explorez d'autres cellules d'eau, mais aucun composant connecté n'a un nombre total de poissons plus élevé.
3. Sortie: 7.

Complexité du temps:

• DFS Traversion: Chaque cellule est visitée une fois → O (m × n).
• Complexité globale: o (m × n), où m et n sont des dimensions de la grille.

Sortie pour les exemples:

• Exemple 1: 7
• Exemple 2: 1

La solution utilise efficacement le DFS pour explorer les composants connectés des cellules d'eau et calcule le poisson maximal capable de faire par un pêcheur à partir de toute cellule d'eau. Cette approche garantit une exploration optimale et fonctionne bien pour les contraintes données.

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• LinkedIn
• github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!