ขนาดตารางเมทริกซ์ย่อยสูงสุดที่มี 1s . ทั้งหมด

เมื่อให้เมทริกซ์ไบนารี หน้าที่ของเราคือค้นหาเมทริกซ์สี่เหลี่ยมจัตุรัสที่มีองค์ประกอบทั้งหมดเป็น 1

สำหรับปัญหานี้ เราจะสร้างเมทริกซ์ขนาดเสริม ซึ่งลำดับจะเหมือนกับเมทริกซ์ที่กำหนด เมทริกซ์ขนาดนี้จะช่วยแสดง ในแต่ละรายการ Size[i, j] คือขนาดของเมทริกซ์สี่เหลี่ยมจัตุรัสที่มี 1s ทั้งหมด จากเมทริกซ์ขนาดนั้น เราจะได้จำนวนสูงสุดเพื่อให้ได้ขนาดของเมทริกซ์กำลังสองที่ใหญ่ที่สุด

อินพุตและเอาต์พุต

Input:
The binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output:
The largest submatrix with all 1’s.

อัลกอริทึม

subMatWithOne(given matrix)

ป้อนข้อมูล - เมทริกซ์หลัก

ผลลัพธ์ − แสดงเมทริกซ์สี่เหลี่ยมจัตุรัสด้วย 1 อันใดอันหนึ่งที่ใหญ่ที่สุด

Begin
   define subMat whose order is same as given matrix
   copy first row and first column of given matrix to subMat

   for all row i (1 to n), do
      for all column j (1 to n), do
         if matrix[i, j] = 1, then
            subMat[i, j] := 1 + minimum of subMat[i, j-1]
            and subMat[i-1, j-1]
         else
            subMat[i, j] := 0
      done
   done

   maxSize := subMat[0, 0], iMax := 0 and jMax := 0
   for all row i and column j, do
      if maxSize < subMat[i, j], then
         maxSize := subMat[i, j]
         iMax := i, jMax := j
   done

   print sub matrix from row = iMax to (iMax - maxSize), and column jMax to (jMax - maxSize)
End

ตัวอย่าง

#include<iostream>
#define ROW 6
#define COL 5
using namespace std;

int matrix[ROW][COL] =  {
   {0, 1, 1, 0, 1},
   {1, 1, 0, 1, 0},
   {0, 1, 1, 1, 0},
   {1, 1, 1, 1, 0},
   {1, 1, 1, 1, 1},
   {0, 0, 0, 0, 0}
};

int min(int a, int b, int c) {
   return ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

void subMatWithOne() {
   int subMat[ROW][COL];
   int maxSize, iMax, jMax;

   for(int i = 0; i < ROW; i++)    //copy first row of matrix to sub matrix
      subMat[i][0] = matrix[i][0];

   for(int j = 0; j < COL; j++)    //copy first column of matrix to sub matrix
      subMat[0][j] = matrix[0][j];

   for(int i = 1; i < ROW; i++) {
      for(int j = 1; j < COL; j++) {
         if(matrix[i][j] == 1)    //find minimum of left, top and diagonal element + 1
            subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
         else
            subMat[i][j] = 0;    //if item is 0, put only 0
      }  
   }

   maxSize = subMat[0][0]; iMax = 0; jMax = 0;
   for(int i = 0; i < ROW; i++) {    //find the order of sub square matrix

      for(int j = 0; j < COL; j++) {
         if(maxSize < subMat[i][j]) {

            maxSize = subMat[i][j];
            iMax = i;
            jMax = j;
         }      
      }                
   }  
 
   cout << "Subsquare matrix: "<<endl;
   for(int i = iMax; i > iMax - maxSize; i--) {    //print the submatrix using max size
      for(int j = jMax; j > jMax - maxSize; j--) {
         cout << matrix[i][j]<<" ";
      }
      cout << endl;
   }
}  
 
int main() {
   subMatWithOne();
} 

ผลลัพธ์

Subsquare matrix:
1 1 1
1 1 1
1 1 1