इस समस्या में, हमें NxN बाइनरी मैट्रिक्स bin[][] दिया गया है। हमारा कार्य बाइनरी मैट्रिक्स में सभी 1s से बने सबसे बड़े '+' का आकार खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
0 1 1 1 1 1 0 1 0
आउटपुट
5
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान सबसे बड़े '+' को खोजना है जिसके लिए हमें मैट्रिक्स में एक बिंदु के लिए एक दिशा में 1s की अधिकतम संख्या ज्ञात करनी होगी जो दिए गए 1 के लिए सभी चार दिशाओं में समान होनी चाहिए। इसके लिए, हम बिंदु के प्रत्येक तरफ के लिए एक मैट्रिक्स बनाएंगे यानी 4। प्रत्येक दिए गए तत्व के लिए लगातार 1s की संख्या स्टोर करेगा। सभी इंडेक्स मानों के लिए, हम अधिकतम मान ढूंढेंगे जो सभी चार दिशाओं में लगातार 1s का न्यूनतम है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
