इस समस्या में, हमें nXm आकार का 2-डी मैट्रिक्स दिया गया है जिसमें केवल 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 है।
समाधान दृष्टिकोण -
समस्या को हल करने के लिए, हमें बस मैट्रिक्स के कनेक्टेड सेल की कुल संख्या की गणना करने की आवश्यकता है।
इसके लिए, हम सेल के लिए डीएफएस करेंगे जो वर्तमान सेल के सभी पड़ोसी कोशिकाओं की जांच करेगा (एक सेल के लिए 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