資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告