इस समस्या में, हमें एक NxN बाइनरी मैट्रिक्स बिन [] [] दिया जाता है। हमारा काम बाइनरी मैट्रिक्स में सभी के द्वारा बनाए गए सबसे बड़े '+' के आकार का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
0 1 1 1 1 1 0 1 0
आउटपुट
5
समाधान दृष्टिकोण
समस्या का एक सरल समाधान सबसे बड़ा '+' ज्ञात करना है जिसके लिए हमें मैट्रिक्स में एक बिंदु के लिए एक दिशा में अधिकतम 1 की संख्या ज्ञात करनी होगी, जो किसी दिए गए 1 के लिए चारों दिशाओं में समान होना चाहिए। इसके लिए, हम बिंदु के प्रत्येक पक्ष के लिए एक मैट्रिक्स बनाएंगे यानी 4. प्रत्येक दिए गए तत्व के लिए लगातार 1 की संख्या संग्रहीत करेगा। सभी अनुक्रमणिका मानों के लिए, हम अधिकतम मान पाएंगे जो चारों दिशाओं में सभी क्रमागत मानों का न्यूनतम है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
for (int i = 0; i < N; i++) {
conOneTop[0][i] = mat[0][i];
conOneBottom[N - 1][i] = mat[N - 1][i];
conOneLeft[i][0] = mat[i][0];
conOneRight[i][N - 1] = mat[i][N - 1];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (mat[i][j] == 1)
conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
else
conOneLeft[i][j] = 0;
if (mat[j][i] == 1)
conOneTop[j][i] = conOneTop[j - 1][i] + 1;
else
conOneTop[j][i] = 0;
j = N - 1 - j;
if (mat[j][i] == 1)
conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
else
conOneBottom[j][i] = 0;
if (mat[i][j] == 1)
conOneRight[i][j] = conOneRight[i][j + 1] + 1;
else
conOneRight[i][j] = 0;
j = N - 1 - j;
}
}
int maxConOne = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
int ConOnes = min(min(conOneTop[i][j],
conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
if(ConOnes > maxConOne)
maxConOne = ConOnes;
}
}
if (maxConOne)
return (4 * (maxConOne - 1) + 1);
return 0;
}
int main() {
int mat[N][N] = {
{ 1, 0, 1, 1, 1, 1, 0 },
{ 1, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
};
cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
return 0;
} आउटपुट
The size of the largest plus formed by ones is 9