查找“X”形图案的总数

---

在这个问题中，我们需要找到给定矩阵中“X”形图案的总数。我们可以使用一个或多个相邻的“X”元素来构造单个“X”形图案。

我们可以使用 DFS（深度优先搜索）技术来解决这个问题。对于每个“X”元素，我们可以使用 DFS 找到所有相邻元素，并将其计为一个“X”形图案。如果我们找到一个新的“X”，我们将再次找到其相邻元素。

这里，我们将使用迭代和递归 DFS 来找到“X”形图案的总数。

问题陈述 - 我们给定一个大小为 N*M 的矩阵[]，其中包含“X”和“O”字符。我们需要找到给定矩阵中“X”形图案的总数。一个“X”形图案包含一个或多个垂直和水平相邻的“X”元素。

示例

输入

matrix = {{'O', 'O', 'X'}, {'O', 'X', 'X'}, {'X', 'X', 'X'}}

输出

1

解释 - 这里，所有 X 都是相邻的。因此，我们只能创建一个形状。

O O X
O X X
O X X

输入

matrix = {{'X', 'O', 'X'}, {'O', 'O', 'X'}, {'X', 'X', 'X'}}

输出

2

解释

The first shape is :-
X O O
O - -
- - -
The second shape is :-
- O X 
O O X
X X X

方法 1

在这种方法中，我们将使用递归 DFS 技术来找到给定矩阵中“X”形图案的总数。

算法

步骤 1 - 将“cnt”初始化为 0，以存储“X”形图案总数。

步骤 2 - 使用两个嵌套循环开始遍历矩阵。

步骤 3 - 如果当前元素是“X”，则将“cnt”加 1，并执行 performDFS() 函数以将所有相邻的“X”替换为“O”。

步骤 4 - 定义 performDFS() 函数。

步骤 4.1 - 如果索引 p 小于 0，q 小于 0，p 大于矩阵的总行数，或 q 大于矩阵的总行数，则执行 return 语句。

步骤 4.2 - 如果 matrix[p][q] 是“X”，则将其更新为“O”。

步骤 4.3 - 对所有 4 个方向进行递归调用，以访问相邻的“X”元素。

步骤 5 - 返回“cnt”值。

示例

#include <bits/stdc++.h>
using namespace std;

void performDFS(vector<vector<char>> &matrix, int p, int q) {
    if (p < 0 || q < 0 || p >= matrix.size() || matrix[p].size() <= q) {
        return;
    }
    if (matrix[p][q] == 'X') {
        // Update element with 'O'
        matrix[p][q] = 'O';
        // Recursively call DFS in all 4 directions
        performDFS(matrix, p + 1, q);
        performDFS(matrix, p, q + 1);
        performDFS(matrix, p - 1, q);
        performDFS(matrix, p, q - 1);
    }
}
int findXShape(vector<vector<char>> &matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int cnt = 0;
    for (int p = 0; p < matrix.size(); p++) {
        for (int q = 0; q < matrix[p].size(); q++) {
            // performing DFS on each element having a value 'X'
            if (matrix[p][q] == 'X') {
                cnt++;
                performDFS(matrix, p, q);
            }
        }
    }
    return cnt;
}
int main() {
    vector<vector<char>> matrix = {{'O', 'O', 'X'},
                                   {'O', 'X', 'X'},
                                   {'X', 'X', 'X'}};
    cout << "The total number of X shape in the given matrix is " << findXShape(matrix) << endl;
    return 0;
}

输出

The total number of X shape in the given matrix is 1

时间复杂度 - O(N*M*N*M)，其中 (N*M) 用于矩阵遍历，O(N*M) 用于执行 DFS。

空间复杂度 - O(1)，因为我们没有使用任何额外的空间。

方法 2

在这种方法中，我们将使用“while”循环执行深度优先搜索。此外，我们将使用堆栈数据结构来跟踪最后访问的数组元素。

算法

步骤 1 - 将“cnt”初始化为 0，并使用两个嵌套循环遍历给定矩阵。

步骤 2 - 如果当前元素是“X”，则将“cnt”值加 1，并执行 performDFS() 函数。

步骤 3.1 - 在 performDFS() 函数中，定义“pairSt”堆栈并将 {0, 0} 推入堆栈。

步骤 3.2 - 遍历堆栈，直到其变为空。

步骤 3.3 - 从堆栈中弹出顶部元素，并将它的第一个和第二个元素分别存储到“x”和“y”变量中。

步骤 3.4 - 如果当前元素是“X”，则将其更新为“O”。

步骤 3.5 - 如果存在任何相邻的“X”元素，则将索引推入堆栈。

步骤 4 - 返回“cnt”值。

示例

#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int k){
   int totalSum = 0;
   // Deques to store indices of the current window in increasing and decreasing order, respectively;
   deque<int> inc(k), dec(k);
   // Handling the first window
   int p = 0;
   for (p = 0; p < k; p++){
      // Remove elements which are greater than the current element
      while ((!inc.empty()) && nums[inc.back()] >= nums[p])
      inc.pop_back();
      // Remove elements from dec deque which are smaller than the current element
      while ((!dec.empty()) && nums[dec.back()] <= nums[p])
      dec.pop_back(); // Remove from rear
      // Add the nums[p] at last
      inc.push_back(p);
      dec.push_back(p);
   }
   // Hanlding other windows
   for (; p < len; p++){
      // get the first element from both the queues, and add them
      totalSum += nums[inc.front()] + nums[dec.front()];
      // Removing elements of the previous window
      while (!inc.empty() && inc.front() <= p - k)
      inc.pop_front();
      while (!dec.empty() && dec.front() <= p - k)
      dec.pop_front();
      while ((!inc.empty()) && nums[inc.back()] >= nums[p])
      inc.pop_back();
      while ((!dec.empty()) && nums[dec.back()] <= nums[p])
      dec.pop_back();
      inc.push_back(p);
      dec.push_back(p);
   }
   // Last window sum
   totalSum += nums[inc.front()] + nums[dec.front()];
   return totalSum;
}
int main() {
   int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
   int len = sizeof(nums) / sizeof(nums[0]);
   int K = 4;
   cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
   return 0;
}

输出

The ans of minimum and maximum elements of all subarrays of size K is 15

时间复杂度 - O(N*M*N*M)，其中 (N*M) 用于遍历矩阵，O(N*M) 用于执行 DFS。

空间复杂度 - O(N*M)，用于在矩阵中存储索引对。

我们学习了如何在矩阵中实现迭代和递归 DFS。有时，在矩阵中实现 DFS 来解决与矩阵相关的复杂问题也很有用。