C++ program to find if pattern exists in grid

Suppose we have an n * n grid. We need to detect whether there is a cross-shaped pattern in the grid, as shown below −

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

The grid can only contain '#' and '.'. We need to detect the pattern and find out how many of these Pattern in grid. The grid and dimensions are given to us as input.

Problem Category

Various problems in programming can be solved through different techniques. To solve a problem, we first have to design an algorithm and study the specific problem in detail. If the same problem occurs repeatedly, recursive methods can be used; alternatively, we can also use iterative structures. Control statements such as if-else and switch case can be used to control the logical flow of the program. Effective use of variables and data structures can provide a simpler solution and a lightweight, low memory requirement program. We have to study existing programming techniques like divide and conquer, greedy programming, dynamic programming and find out if they can be used. This problem can be solved with some basic logic or brute force methods. Please follow the below to better understand this method.

So, if our problem input is n = 5 and the grid is

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

then the output will be 1.

Steps

To solve this problem, we will follow the following steps:

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)

Example

Let us see the implementation below for better understanding −

#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

The above is the detailed content of C++ program to find if pattern exists in grid. For more information, please follow other related articles on the PHP Chinese website!