Compter les cellules non gardées dans la grille-tutoriel php-php.cn

Compter les cellules non gardées dans la grille

Susan Sarandon

Libérer： 2024-11-22 17:32:17

original

551 Les gens l'ont consulté

2257. Comptez les cellules non gardées dans la grille

Difficulté :Moyen

Sujets :Tableau, Matrice, Simulation

Vous recevez deux entiers m et n représentant une grille indexée à 0 m x n. Vous recevez également deux tableaux d'entiers 2D guards et murs où guards[i] = [row_i, col_i] et murs[j] = [row_j, col_j] représentent les positions de la i^ème garde et j^ème mur respectivement.

Un garde peut voir chaque cellule dans les quatre directions cardinales (nord, est, sud ou ouest) à partir de sa position à moins obstruée par un mur ou un autre garde. Une cellule est gardée s'il y a au moins un gardien qui peut la voir.

Renvoyer le nombre de cellules inoccupées qui ne sont non gardées.

Exemple 1 :

Count Unguarded Cells in the Grid

Entrée : m = 4, n = 6, gardes = [[0,0],[1,1],[2,3]], murs = [[0,1],[2, 2],[1,4]]
Sortie :7
Explication : Les cellules gardées et non gardées sont représentées respectivement en rouge et vert dans le schéma ci-dessus.
- Il y a un total de 7 cellules non gardées, donc nous en rendons 7.

Exemple 2 :

Count Unguarded Cells in the Grid

Entrée : m = 3, n = 3, gardes = [[1,1]], murs = [[0,1],[1,0],[2,1],[1, 2]]
Sortie : 4
Explication : Les cellules non gardées sont représentées en vert dans le schéma ci-dessus.
- Il y a un total de 4 cellules non gardées, donc nous en rendons 4.

Contraintes :

1 <= m, n <= 10⁵
2 <= m * n <= 10⁵
1 <= guards.length, murs.length <= 5 * 10⁴
2 <= guards.length murs.length <= m * n
gardes[i].length == murs[j].length == 2
0 <= ligne_i, ligne_j < m
0 <= col_i, col_j < n
Toutes les positions dans les gardes et les murs sont uniques.

Indice :

Créez un tableau 2D pour représenter la grille. Pouvez-vous marquer les tuiles visibles par un gardien ?
Parcourez les gardes, et pour chacune des 4 directions, avancez la tuile actuelle et marquez la tuile. Quand faut-il arrêter d'avancer ?

Solution :

Nous devons marquer les cellules qui sont gardées par au moins un gardien. Les gardes peuvent voir dans quatre directions cardinales (nord, sud, est et ouest), mais leur vision est bloquée par des murs. Nous pouvons simuler ce processus et compter le nombre de cellules non gardées.

Approche:

Créer une grille : Nous pouvons représenter la grille comme un tableau 2D où chaque cellule peut être soit un mur, un garde ou vide.
Marquer les cellules gardées : Pour chaque garde, itérer dans les quatre directions (nord, sud, est, ouest) et marquer toutes les cellules qu'il peut voir, en s'arrêtant lorsque l'on rencontre un mur ou un autre garde.
Comptez les cellules non gardées : Après avoir marqué les cellules gardées, comptez combien de cellules ne sont pas gardées et ne sont pas des murs.

Mesures:

Initialisation de la grille : Créez un tableau 2D pour représenter la grille. Marquez les cellules avec des murs, des gardes et des zones gardées au fur et à mesure de notre itération.
Simulation de la couverture de garde :
- Les gardes peuvent voir dans quatre directions (nord, sud, est, ouest).
- Marquer les cellules gardées par chaque garde jusqu'à rencontrer un mur ou un autre garde.
Comptage des cellules non gardées : Après avoir traité tous les gardes, comptez les cellules qui ne sont ni des murs, ni des gardes, ni gardées.

Implémentons cette solution en PHP : 2257. Compter les cellules non gardées dans la grille

Explication:

Initialisation :
- La grille est initialisée à 0 pour les cellules vides. Les murs et les gardes sont marqués de constantes uniques.
Simulation de garde :
- Pour chaque garde, simulez un mouvement dans les quatre directions, en marquant les cellules comme gardées jusqu'à ce qu'elles heurtent un mur ou un autre garde.
Comptage des cellules non gardées :
- Après avoir traité toutes les gardes, parcourez la grille et comptez les cellules toujours marquées comme 0.

Performance:

Complexité temporelle : O(m x n g x d), où g est le nombre de gardes et d est le nombre de cellules dans la direction dans laquelle chaque garde peut se déplacer.
Complexité spatiale : O(m x n) pour la grille.

Complexité temporelle :

Initialisation de la grille : _O(m * n), où _m et n sont les dimensions de la grille.
Marquage vision de garde : Chaque garde vérifie au maximum la longueur de la ligne ou de la colonne dans les quatre directions. Donc, pour chaque garde, c'est O(m n).
Comptage des cellules non gardées : O(m * n).

Ainsi, la complexité globale est O(m * n), ce qui est efficace compte tenu des contraintes du problème.

Cas extrêmes :

S'il n'y a pas de gardes ou de murs, la grille entière ne sera pas gardée.
Si toutes les cellules sont soit gardées, soit murées, le résultat sera 0 cellule non gardée.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

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