Programme C++ pour trouver si un modèle existe dans la grille

Supposons que nous ayons une grille n*n. Nous devons détecter s'il y a un motif en forme de croix dans la grille, comme indiqué ci-dessous −

#...#
.#.#.
..#..
.#.#.
#...#

La grille ne peut contenir que '#' et '.'. Nous devons détecter la tendance et déterminer combien d'entre eux Modèle en grille. La grille et les dimensions nous sont données en entrée.

Catégories de problèmes

Divers problèmes de programmation peuvent être résolus grâce à différentes techniques. Pour résoudre un problème, nous devons d’abord concevoir un algorithme et étudier le problème spécifique en détail. Si le même problème se produit de manière répétée, des méthodes récursives peuvent être utilisées. Alternativement, nous pouvons également utiliser des structures itératives. Des instructions de contrôle telles que if-else et switch case peuvent être utilisées pour contrôler le flux logique du programme. L'utilisation efficace des variables et des structures de données peut fournir une solution plus simple et un programme léger et nécessitant peu de mémoire. Nous devons étudier les techniques de programmation existantes telles que diviser pour régner, la programmation gourmande, la programmation dynamique et découvrir si elles peuvent être utilisées. Ce problème peut être résolu avec des méthodes logiques de base ou par force brute. Veuillez suivre ce qui suit pour mieux comprendre cette méthode.

Donc, si notre entrée de problème est n = 5 et que la grille est

#...#
.#.#.
..#..
.#.#.
#...#,

alors la sortie sera 1.

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes :

count := 0
for initialize i := 1, when i < n - 1, update (increase i by 1), do:
   for initialize j := 1, when j < n - 1, update (increase j by 1), do:
      if grid[i, j] is same as &#39;#&#39; and grid[i - 1, j - 1] is same as &#39;#&#39; and grid[i - 1, j + 1] is same as &#39;#&#39; and grid[i + 1, j - 1] is same as &#39;#&#39; and grid[i + 1, j + 1] is same as &#39;#&#39;, then:
         (increase count by 1)
print(count)

Exemple

Voyons l'implémentation ci-dessous pour une meilleure compréhension −

#include<bits/stdc++.h>
using namespace std;
void solve(int n, vector<string> grid) {
   int count = 0;
   for(int i = 1; i < n - 1; i++){
      for(int j = 1; j < n - 1; j++){
         if(grid[i][j] == &#39;#&#39; && grid[i - 1][j - 1] == &#39;#&#39; && grid[i - 1][j + 1] == &#39;#&#39; && grid[i + 1][j - 1] == &#39;#&#39; && grid[i + 1][j + 1] == &#39;#&#39;)
            count++;
      }
   }
   cout<< count;
}
int main() {
   int n = 5;
   vector<string> grid = {"#...#", ".#.#.", "..#..", ".#.#.", "#...#"};
   solve(n, grid);
   return 0;
}

Input

5, {"#...#", ".#.#.", "..#..", ".#.#.", "#...#"}

Output

1

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!