給定矩陣“ O”和“ X”，找到被“ X”包圍的最大子正方形 · GeeksForGeeks 中文系列教程

# 給定矩陣“ O”和“ X”，找到被“ X”包圍的最大子正方形 > 原文： [https://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/](https://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/) 給定一個矩陣，其中每個元素均為“ O”或“ X”，請找到被“ X”包圍的最大子正方形。在下面的文章中，假定給定矩陣也是方陣。下面給出的代碼可以很容易地擴展到矩形矩陣。 **示例**： ``` Input: mat[N][N] = { {'X', 'O', 'X', 'X', 'X'}, {'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'O', 'X', 'O'}, {'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'O'}, }; Output: 3 The square submatrix starting at (1, 1) is the largest submatrix surrounded by 'X' Input: mat[M][N] = { {'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'O', 'X'}, {'X', 'X', 'X', 'O', 'O', 'X'}, {'X', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, }; Output: 4 The square submatrix starting at (0, 2) is the largest submatrix surrounded by 'X' ``` 一種**簡單解決方案**是考慮每個正方形子矩陣，并檢查是否所有角邊都填充有“ X”。該解決方案的時間復雜度為 O（N <sup>4</sup> ）。我們可以在 O（N <sup>3</sup> ）時間中使用額外的空間來解決此問題**。這個想法是創建兩個輔助數組 hor [N] [N]和 ver [N] [N]。存儲在 hor [i] [j]中的值是直到 mat [] []中的 mat [i] [j]為止的水平連續'X'字符數。同樣，存儲在 ver [i] [j]中的值是直到 mat [] []中的 mat [i] [j]為止的垂直連續“ X”字符數。以下是一個示例。** ``` mat[6][6] = X O X X X X X O X X O X X X X O O X O X X X X X X X X O X O O O X O O O hor[6][6] = 1 0 1 2 3 4 1 0 1 2 0 1 1 2 3 0 0 1 0 1 2 3 4 5 1 2 3 0 1 0 0 0 1 0 0 0 ver[6][6] = 1 0 1 1 1 1 2 0 2 2 0 2 3 1 3 0 0 3 0 2 4 1 1 4 1 3 5 0 2 0 0 0 6 0 0 0 ``` 一旦我們在 hor [] []和 ver [] []中填充了值，就從矩陣的最右下角開始，并逐行地移到最左上角。對于每個訪問的入口 mat [i] [j]，我們比較 hor [i] [j]和 ver [i] [j]的值，并選擇兩個中較小的一個作為正方形。假設其中兩個較小的為“小”。選擇兩個較小的值后，我們分別檢查 ver [] []和 hor [] []的左邊緣和上邊緣。如果他們有相同的條目，那么我們找到了一個子正方形。否則，我們嘗試使用 small-1。以下是上述想法的實現。 ## C++ ```cpp // A C++ program to find? the largest subsquare // surrounded by 'X' in a given matrix of 'O' and 'X' #include<iostream> using namespace std; // Size of given matrix is N X N #define N 6 // A utility function to find minimum of two numbers int getMin(int x, int y) { return (x<y)? x: y; } // Returns size of maximum size subsquare matrix // surrounded by 'X' int findSubSquare(int mat[][N]) { ????int max = 0; // Initialize result ????// Initialize the left-top value in hor[][] and ver[][] ????int hor[N][N], ver[N][N]; ????hor[0][0] = ver[0][0] = (mat[0][0] == 'X'); ????// Fill values in hor[][] and ver[][] ????for (int i=0; i<N; i++) ????{ ????????for (int j=0; j<N; j++) ????????{ ????????????if (mat[i][j] == 'O') ????????????????ver[i][j] = hor[i][j] = 0; ????????????else ????????????{ ????????????????hor[i][j] = (j==0)? 1: hor[i][j-1] + 1; ????????????????ver[i][j] = (i==0)? 1: ver[i-1][j] + 1; ????????????} ????????} ????} ????// Start from the rightmost-bottommost corner element and find ????// the largest ssubsquare with the help of hor[][] and ver[][] ????for (int i = N-1; i>=1; i--) ????{ ????????for (int j = N-1; j>=1; j--) ????????{ ????????????// Find smaller of values in hor[][] and ver[][] ????????????// A Square can only be made by taking smaller ????????????// value ????????????int small = getMin(hor[i][j], ver[i][j]); ????????????// At this point, we are sure that there is a right ????????????// vertical line and bottom horizontal line of length ????????????// at least 'small'. ????????????// We found a bigger square if following conditions ????????????// are met: ????????????// 1)If side of square is greater than max. ????????????// 2)There is a left vertical line of length >= 'small' ????????????// 3)There is a top horizontal line of length >= 'small' ????????????while (small > max) ????????????{ ????????????????if (ver[i][j-small+1] >= small && ????????????????????hor[i-small+1][j] >= small) ????????????????{ ????????????????????max = small; ????????????????} ????????????????small--; ????????????} ????????} ????} ????return max; } // Driver program to test above function int main() { ????int mat[][N] =? {{'X', 'O', 'X', 'X', 'X', 'X'}, ?????????????????????{'X', 'O', 'X', 'X', 'O', 'X'}, ?????????????????????{'X', 'X', 'X', 'O', 'O', 'X'}, ?????????????????????{'O', 'X', 'X', 'X', 'X', 'X'}, ?????????????????????{'X', 'X', 'X', 'O', 'X', 'O'}, ?????????????????????{'O', 'O', 'X', 'O', 'O', 'O'}, ????????????????????}; ????cout << findSubSquare(mat); ????return 0; } ```