이진 정사각형 행렬의 모든 1로 구성된 가장 큰 플러스 또는 '+'

주어진 n × n 함께 로 구성된 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(각 방향 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) 공간

그만큼 아이디어 4개의 보조 행렬을 유지하는 것입니다 왼쪽[][] 오른쪽[][] 위쪽[][] 아래쪽[][] 모든 방향에서 연속된 1을 저장합니다. 각 셀에 대해 (나는 j) 입력 행렬에서 우리는 아래에 정보를 저장합니다. 네 행렬 -
왼쪽(i j) 연속된 1의 최대 개수를 왼쪽 셀(i j)을 포함하는 셀(i j)의.
그렇죠(i j) 연속된 1의 최대 개수를 오른쪽 셀(i j)을 포함하는 셀(i j)의.
탑(i j) 연속된 1의 최대 수를 저장합니다. 맨 위 셀(i j)을 포함하는 셀(i j)의.
바닥(i j) 연속된 1의 최대 수를 저장합니다. 맨 아래 셀(i j)을 포함하는 셀(i j)의.

위 행렬의 각 셀에 대한 값을 계산한 후 가장 큰'+' 의 최소값을 고려하여 최대값을 갖는 입력 행렬의 셀로 구성됩니다. 왼쪽(i j) 오른쪽(i j) 위쪽(i j) 아래쪽(i j) )

우리는 사용할 수 있습니다 동적 프로그래밍 모든 방향에서 연속된 1의 총 개수를 계산하려면 다음을 수행하세요.

mat(i j) == 1인 경우
왼쪽(i j) = 왼쪽(i j - 1) + 1
그렇지 않으면 왼쪽(i j) = 0
Java에서 null을 확인하십시오.

mat(i j) == 1인 경우
상단(i j) = 상단(i - 1 j) + 1;
그렇지 않으면 top(i j) = 0;

mat(i j) == 1인 경우
하단(i j) = 하단(i + 1 j) + 1;
그렇지 않으면 하단(i j) = 0;

mat(i j) == 1인 경우
오른쪽(i j) = 오른쪽(i j + 1) + 1;
그렇지 않으면 right(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# 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));

산출

시간 복잡도: O(n²) 방향 행렬을 계산하기 위한 4개의 패스와 가장 큰 '+'를 결정하기 위한 1개의 최종 패스로 인해 발생합니다. 각 패스에는 O(n²) 시간이 걸리므로 전체 복잡성은 O(n²)입니다.
공간 복잡도: O(n²) 4개의 보조 행렬(왼쪽 오른쪽 위 아래)이 O(n²) 추가 공간을 소비하기 때문입니다.