假设我们有一个 n * n 的网格。我们需要检测网格中是否存在十字形的模式，如下所示 −

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

网格只能包含 '#' 和 '.'。我们需要检测模式并找出有多少个这样的 模式在网格中。网格和维度作为输入给我们。

问题类别

编程中的各种问题可以通过不同的技术来解决。要解决一个问题，我们首先必须设计一个算法，并且要详细研究特定的问题。如果同一个问题反复出现，可以使用递归方法；另外，我们也可以使用迭代结构。控制语句如if-else和switch case可以用来控制程序中的逻辑流程。有效地使用变量和数据结构可以提供更简单的解决方案和一个轻量级、低内存需求的程序。我们必须研究现有的编程技术，如分而治之、贪婪编程、动态规划，并找出它们是否可以使用。这个问题可以通过一些基本的逻辑或蛮力方法来解决。请按照以下内容来更好地理解这种方法。

所以，如果我们的问题输入是n = 5，网格为

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

然后输出将为1。

步骤

为了解决这个问题，我们将按照以下步骤进行：

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 '#' and grid[i - 1, j - 1] is same as '#' and grid[i - 1, j + 1] is same as '#' and grid[i + 1, j - 1] is same as '#' and grid[i + 1, j + 1] is same as '#', then:
         (increase count by 1)
print(count)

Example

让我们看下面的实现以更好地理解−

#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] == '#' && grid[i - 1][j - 1] == '#' && grid[i - 1][j + 1] == '#' && grid[i + 1][j - 1] == '#' && grid[i + 1][j + 1] == '#')
            count++;
      }
   }
   cout<< count;
}
int main() {
   int n = 5;
   vector<string> grid = {"#...#", ".#.#.", "..#..", ".#.#.", "#...#"};
   solve(n, grid);
   return 0;
}

输入

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

输出

1