在C ++中找到布尔矩阵中最大区域的长度
在这个问题中，我们得到一个大小为nXm的二维矩阵，仅由0和1组成。我们的任务是在布尔矩阵中找到最大区域的长度。
问题描述： 如果一个单元格包含1，则它是一个已填充的单元格。 我们需要找到水平或垂直或对角线彼此相邻连接的连接单元的长度。
让我们举个例子来了解这个问题，
输入： 矩阵[4] [5]
{{0，1，1，0，1}，
{0，0，1，1，1}，
{1，0，0，0，0}，
{1，0，1，0，1}}
输出： 6
解释：
连接的填充单元数为1、2、6。
解决方法-
为了解决这个问题，我们只需要计算矩阵连接单元的总数。
为此，我们将对该单元执行DFS，这将检查当前单元的所有相邻单元（对于一个单元，可以有8个相邻单元）。对于每个单元格，我们需要通过使用哈希图进行跟踪来检查是否已访问它。 完成后，我们需要返回访问单元的最大数量。
该程序说明了我们解决方案的工作原理，
示例
#include <bits/stdc++.h>输出结果using namespace std;
#define ROW 4
#define COL 5
int isNotVisited(int M[][COL], int row, int col, bool visited[][COL]) {
return (row >= 0) && (row < ROW) && (col >= 0 ) && (col < COL) && (M[row][col] && !visited[row][col]);
}
void depthFirstSearch(int M[][COL], int row, int col, bool visited[][COL], int& count){
static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
visited[row][col] = true;
for (int k = 0; k < 8; ++k) {
if (isNotVisited(M, row + rowNbr[k], col + colNbr[k], visited)) {
count++;
depthFirstSearch(M, row + rowNbr[k], col + colNbr[k], visited, count);
}
}
}
int findLargestRegionLength(int M[][COL]) {
bool isvisited[ROW][COL];
memset(isvisited, 0, sizeof(isvisited));
int maxCount = -1;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
if (M[i][j] && !isvisited[i][j]) {
int count = 1;
depthFirstSearch(M, i, j, isvisited, count);
maxCount = max(maxCount, count);
}
}
}
return maxCount;
}
int main(){
int M[][COL] = { {0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},
{1, 0, 0, 0, 0},
{1, 0, 1, 0, 1} };
cout<<"最大区域的长度是 "<<findLargestRegionLength(M);
return 0;
}
最大区域的长度是 6
以上是 在C ++中找到布尔矩阵中最大区域的长度 的全部内容， 来源链接： utcz.com/z/314291.html
