أكبر علامة زائد أو "+" مكونة من جميع العناصر الموجودة في مصفوفة مربعة ثنائية
نظرا ل ن × ن مصفوفة ثنائية جنبا إلى جنب مع تتكون من 0 ثانية و 1 ثانية . مهمتك هي العثور على حجم الأكبر "+" الشكل الذي يمكن تشكيله باستخدام فقط 1 ثانية .
أ "+" يتكون الشكل من خلية مركزية لها أربعة أذرع تمتد في الاتجاهات الأربعة ( لأعلى ولأسفل لليسار ولليمين ) مع البقاء داخل حدود المصفوفة. حجم أ "+" يتم تعريفه على أنه العدد الإجمالي للخلايا تشكيلها بما في ذلك المركز وجميع الأذرع.
المهمة هي إرجاع الحد الأقصى للحجم من أي صالحة "+" في جنبا إلى جنب مع . إذا لا "+" يمكن تشكيل العودة .
أمثلة:
مدخل: مع = [ [0 1 1 0 1] [0 0 1 1 1] [1 1 1 1 1] [1 1 1 0 1] [0 1 1 1 0] ]
الإخراج: 9
توضيح: يمكن تشكيل "+" بطول ذراع 2 (خليتان في كل اتجاه + 1 مركز) في وسط الحصيرة.
0 1 1 0 1
0 0 1 1 1
1 1 1 1 1
1 1 1 0 1
0 1 1 1 0
الحجم الإجمالي = (2 × 4) + 1 = 9مدخل: مع = [ [0 1 1] [0 0 1] [1 1 1] ]
الإخراج: 1
توضيح: يمكن تكوين "+" بطول ذراع 0 (0 خلايا في كل اتجاه + 1 مركز) باستخدام أي من الأرقام 1.مدخل: مع = [ [0] ]
الإخراج:
توضيح: لا يمكن تشكيل علامة "+".
[نهج ساذج] - اعتبر كل نقطة كمركز - O(n^4) الزمن وO(n^4) الفضاء
اجتياز خلايا المصفوفة واحدة تلو الأخرى. اعتبر كل نقطة تم اجتيازها كمركز لعلامة الجمع وابحث عن حجم علامة +. لكل عنصر نجتاز اليسار واليمين والأسفل وما فوق. أسوأ حالة في هذا الحل تحدث عندما يكون لدينا كل الأرقام 1.
[النهج المتوقع] - حساب 4 صفائف مسبقًا - O(n^2) الوقت وO(n^2) الفضاء
ال فكرة هو الحفاظ على أربع مصفوفات مساعدة يسار[][] يمين[][] أعلى[][] أسفل[][] لتخزين 1 متتالية في كل اتجاه. لكل خلية (ط ي) في مصفوفة الإدخال نقوم بتخزين المعلومات أدناه في هذه أربعة المصفوفات -
- اليسار (ط ي) يخزن الحد الأقصى لعدد 1 المتتالية إلى غادر من الخلية (i j) بما في ذلك الخلية (i j).
- حق (ط ي) يخزن الحد الأقصى لعدد 1 المتتالية إلى يمين من الخلية (i j) بما في ذلك الخلية (i j).
- أعلى (ط ي) يخزن الحد الأقصى لعدد 1 المتتالية في قمة من الخلية (i j) بما في ذلك الخلية (i j).
- أسفل (ط ي) يخزن الحد الأقصى لعدد 1 المتتالية في قاع من الخلية (i j) بما في ذلك الخلية (i j).
بعد حساب القيمة لكل خلية من المصفوفات المذكورة أعلاه الأكبر'+' سيتم تشكيلها بواسطة خلية من مصفوفة الإدخال التي لها قيمة قصوى من خلال النظر في الحد الأدنى من ( اليسار (i j) اليمين (i j) الأعلى (i j) الأسفل (i j) )
يمكننا استخدامها البرمجة الديناميكية لحساب المبلغ الإجمالي للرقم 1 المتتالي في كل اتجاه:
إذا حصيرة (ط ي) == 1
اليسار(i j) = اليسار(i j - 1) + 1آخر اليسار (ط ي) = 0
إذا حصيرة (ط ي) == 1
top(i j) = top(i - 1 j) + 1;آخر أعلى (ط ي) = 0؛
إذا حصيرة (ط ي) == 1
أسفل(i ي) = أسفل(i + 1 ي) + 1;آخر أسفل (ط ي) = 0؛
إذا حصيرة (ط ي) == 1
يمين(i ي) = يمين(ي ي + 1) + 1;آخر صحيح (i j) = 0؛
فيما يلي تنفيذ النهج أعلاه:
C++ // C++ program to find the largest '+' in a binary matrix // using Dynamic Programming #include using namespace std ; int findLargestPlus ( vector < vector < int >> & mat ) { int n = mat . size (); vector < vector < int >> left ( n vector < int > ( n 0 )); vector < vector < int >> right ( n vector < int > ( n 0 )); vector < vector < int >> top ( n vector < int > ( n 0 )); vector < vector < int >> bottom ( n vector < int > ( n 0 )); // Fill left and top matrices for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] == 1 ) { left [ i ][ j ] = ( j == 0 ) ? 1 : left [ i ][ j - 1 ] + 1 ; top [ i ][ j ] = ( i == 0 ) ? 1 : top [ i - 1 ][ j ] + 1 ; } } } // Fill right and bottom matrices for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] == 1 ) { right [ i ][ j ] = ( j == n - 1 ) ? 1 : right [ i ][ j + 1 ] + 1 ; bottom [ i ][ j ] = ( i == n - 1 ) ? 1 : bottom [ i + 1 ][ j ] + 1 ; } } } int maxPlusSize = 0 ; // Compute the maximum '+' size for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] == 1 ) { int armLength = min ({ left [ i ][ j ] right [ i ][ j ] top [ i ][ j ] bottom [ i ][ j ]}); maxPlusSize = max ( maxPlusSize ( 4 * ( armLength - 1 )) + 1 ); } } } return maxPlusSize ; } int main () { // Hardcoded input matrix vector < vector < int >> mat = { { 0 1 1 0 1 } { 0 0 1 1 1 } { 1 1 1 1 1 } { 1 1 1 0 1 } { 0 1 1 1 0 } }; cout < < findLargestPlus ( mat ) < < endl ; return 0 ; }
Java // Java program to find the largest '+' in a binary matrix // using Dynamic Programming class GfG { static int findLargestPlus ( int [][] mat ) { int n = mat . length ; int [][] left = new int [ n ][ n ] ; int [][] right = new int [ n ][ n ] ; int [][] top = new int [ n ][ n ] ; int [][] bottom = new int [ n ][ n ] ; // Fill left and top matrices for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] == 1 ) { left [ i ][ j ] = ( j == 0 ) ? 1 : left [ i ][ j - 1 ] + 1 ; top [ i ][ j ] = ( i == 0 ) ? 1 : top [ i - 1 ][ j ] + 1 ; } } } // Fill right and bottom matrices for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] == 1 ) { right [ i ][ j ] = ( j == n - 1 ) ? 1 : right [ i ][ j + 1 ] + 1 ; bottom [ i ][ j ] = ( i == n - 1 ) ? 1 : bottom [ i + 1 ][ j ] + 1 ; } } } int maxPlusSize = 0 ; // Compute the maximum '+' size for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] == 1 ) { int armLength = Math . min ( Math . min ( left [ i ][ j ] right [ i ][ j ] ) Math . min ( top [ i ][ j ] bottom [ i ][ j ] )); maxPlusSize = Math . max ( maxPlusSize ( 4 * ( armLength - 1 )) + 1 ); } } } return maxPlusSize ; } public static void main ( String [] args ) { // Hardcoded input matrix int [][] mat = { { 0 1 1 0 1 } { 0 0 1 1 1 } { 1 1 1 1 1 } { 1 1 1 0 1 } { 0 1 1 1 0 } }; System . out . println ( findLargestPlus ( mat )); } }
Python # Python program to find the largest '+' in a binary matrix # using Dynamic Programming def findLargestPlus ( mat ): n = len ( mat ) left = [[ 0 ] * n for i in range ( n )] right = [[ 0 ] * n for i in range ( n )] top = [[ 0 ] * n for i in range ( n )] bottom = [[ 0 ] * n for i in range ( n )] # Fill left and top matrices for i in range ( n ): for j in range ( n ): if mat [ i ][ j ] == 1 : left [ i ][ j ] = 1 if j == 0 else left [ i ][ j - 1 ] + 1 top [ i ][ j ] = 1 if i == 0 else top [ i - 1 ][ j ] + 1 # Fill right and bottom matrices for i in range ( n - 1 - 1 - 1 ): for j in range ( n - 1 - 1 - 1 ): if mat [ i ][ j ] == 1 : right [ i ][ j ] = 1 if j == n - 1 else right [ i ][ j + 1 ] + 1 bottom [ i ][ j ] = 1 if i == n - 1 else bottom [ i + 1 ][ j ] + 1 maxPlusSize = 0 # Compute the maximum '+' size for i in range ( n ): for j in range ( n ): if mat [ i ][ j ] == 1 : armLength = min ( left [ i ][ j ] right [ i ][ j ] top [ i ][ j ] bottom [ i ][ j ]) maxPlusSize = max ( maxPlusSize ( 4 * ( armLength - 1 )) + 1 ) return maxPlusSize if __name__ == '__main__' : # Hardcoded input matrix mat = [ [ 0 1 1 0 1 ] [ 0 0 1 1 1 ] [ 1 1 1 1 1 ] [ 1 1 1 0 1 ] [ 0 1 1 1 0 ] ] print ( findLargestPlus ( mat ))
C# // C# program to find the largest '+' in a binary matrix // using Dynamic Programming using System ; class GfG { static int FindLargestPlus ( int [] mat ) { int n = mat . GetLength ( 0 ); int [] left = new int [ n n ]; int [] right = new int [ n n ]; int [] top = new int [ n n ]; int [] bottom = new int [ n n ]; // Fill left and top matrices for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i j ] == 1 ) { left [ i j ] = ( j == 0 ) ? 1 : left [ i j - 1 ] + 1 ; top [ i j ] = ( i == 0 ) ? 1 : top [ i - 1 j ] + 1 ; } } } // Fill right and bottom matrices for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( mat [ i j ] == 1 ) { right [ i j ] = ( j == n - 1 ) ? 1 : right [ i j + 1 ] + 1 ; bottom [ i j ] = ( i == n - 1 ) ? 1 : bottom [ i + 1 j ] + 1 ; } } } int maxPlusSize = 0 ; // Compute the maximum '+' size for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( mat [ i j ] == 1 ) { int armLength = Math . Min ( Math . Min ( left [ i j ] right [ i j ]) Math . Min ( top [ i j ] bottom [ i j ])); maxPlusSize = Math . Max ( maxPlusSize ( 4 * ( armLength - 1 )) + 1 ); } } } return maxPlusSize ; } public static void Main () { // Hardcoded input matrix int [] mat = { { 0 1 1 0 1 } { 0 0 1 1 1 } { 1 1 1 1 1 } { 1 1 1 0 1 } { 0 1 1 1 0 } }; Console . WriteLine ( FindLargestPlus ( mat )); } }
JavaScript // JavaScript program to find the largest '+' in a binary matrix // using Dynamic Programming function findLargestPlus ( mat ) { let n = mat . length ; let left = Array . from ({ length : n } () => Array ( n ). fill ( 0 )); let right = Array . from ({ length : n } () => Array ( n ). fill ( 0 )); let top = Array . from ({ length : n } () => Array ( n ). fill ( 0 )); let bottom = Array . from ({ length : n } () => Array ( n ). fill ( 0 )); // Fill left and top matrices for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] === 1 ) { left [ i ][ j ] = ( j === 0 ) ? 1 : left [ i ][ j - 1 ] + 1 ; top [ i ][ j ] = ( i === 0 ) ? 1 : top [ i - 1 ][ j ] + 1 ; } } } // Fill right and bottom matrices for ( let i = n - 1 ; i >= 0 ; i -- ) { for ( let j = n - 1 ; j >= 0 ; j -- ) { if ( mat [ i ][ j ] === 1 ) { right [ i ][ j ] = ( j === n - 1 ) ? 1 : right [ i ][ j + 1 ] + 1 ; bottom [ i ][ j ] = ( i === n - 1 ) ? 1 : bottom [ i + 1 ][ j ] + 1 ; } } } let maxPlusSize = 0 ; // Compute the maximum '+' size for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { if ( mat [ i ][ j ] === 1 ) { let armLength = Math . min ( left [ i ][ j ] right [ i ][ j ] top [ i ][ j ] bottom [ i ][ j ]); maxPlusSize = Math . max ( maxPlusSize ( 4 * ( armLength - 1 )) + 1 ); } } } return maxPlusSize ; } // Hardcoded input matrix let mat = [ [ 0 1 1 0 1 ] [ 0 0 1 1 1 ] [ 1 1 1 1 1 ] [ 1 1 1 0 1 ] [ 0 1 1 1 0 ] ]; console . log ( findLargestPlus ( mat ));
الإخراج
9
تعقيد الوقت: O(n²) بسبب أربع تمريرات لحساب مصفوفات الاتجاه وتمريرة نهائية واحدة لتحديد أكبر علامة "+". تستغرق كل تمريرة وقتًا O(n²) مما يؤدي إلى تعقيد إجمالي لـ O(n²).
تعقيد الفضاء: O(n²) بسبب وجود أربع مصفوفات مساعدة (يسار يمين أعلى أسفل) تستهلك مساحة إضافية O(n²).
