এই সমস্যায়, আমাদেরকে nXm আকারের একটি 2-D ম্যাট্রিক্স দেওয়া হয়েছে যা শুধুমাত্র 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} }
আউটপুট: ৬
ব্যাখ্যা:
সংযুক্ত ভরাট কক্ষের সংখ্যা হল 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
