इस समस्या में, हमें आकार nXm का एक 2-D मैट्रिक्स दिया गया है जिसमें केवल 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
