极客笔记C++ 找到所有“X”图形的数量
在这个问题中，我们需要找到给定矩阵中所有“X”图形的总数。可以使用1个或多个相邻的“X”元素构建单个“X”图形。
我们可以使用深度优先搜索（DFS）技术来解决这个问题。对于每个“X”元素，我们可以使用DFS找到所有相邻的元素，并将其计数为一个单独的“X”图形。如果我们找到一个新的“X”，则再次找到其相邻的元素。
这里，我们将使用迭代和递归的DFS来找到所有“X”图形的总数。
问题描述：
我们有一个大小为N*M的矩阵matrix[]，其中包含了字符“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
在这种方法中，我们将使用递归的深度优先搜索技术来找到给定矩阵中总共有多少个“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 - 为访问相邻的“X”元素，对所有4个方向进行递归调用。
步骤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(NMNM)，其中(NM)用于矩阵遍历，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来解决与矩阵相关的复杂问题也是很有用的。