数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学在 C++ 中查找布尔矩阵中最大区域的长度
在这个问题中，我们得到一个大小为 nXm 的二维矩阵，它只包含 0 和 1。我们的任务是_查找布尔矩阵中最大区域的长度_。
问题描述：如果一个单元格包含 1，它就是一个_填充单元格_。我们需要找到水平、垂直或对角线连接的连接单元格的长度。
让我们举个例子来理解这个问题，
输入：matrix[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<<"The length of largest region is "<<findLargestRegionLength(M);
return 0;
}输出
The length of largest region is 6
更新于：2021年1月25日
571 次查看
广告