এই সমস্যায়, আমাদের একটি 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