Największy plus lub „+” utworzony przez wszystkie jedyneki w binarnej macierzy kwadratowej

Biorąc pod uwagę n × n macierz binarna wraz z składający się z 0s I 1s . Twoim zadaniem jest znalezienie rozmiaru największego „+” kształt, który można uformować wyłącznie za pomocą 1s .

A „+” kształt składa się z centralnej komórki z czterema ramionami rozciągającymi się we wszystkich czterech kierunkach ( góra dół lewo i prawo ), pozostając w granicach macierzy. Rozmiar A „+” definiuje się jako całkowita liczba komórek tworząc go, łącznie ze środkiem i wszystkimi ramionami.

Zadanie polega na zwróceniu maksymalny rozmiar z jakichkolwiek ważnych „+” W wraz z . Jeśli nie „+” można utworzyć powrót .

Przykłady:

przygotuj się do testowego mockito

Wejście: z = [ [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] ]
Wyjście: 9
Wyjaśnienie: Na środku maty można utworzyć znak „+” o długości ramienia 2 (2 komórki w każdym kierunku + 1 środek).
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
Rozmiar całkowity = (2 × 4) + 1 = 9

Wejście: z = [ [0 1 1] [0 0 1] [1 1 1] ]
Wyjście: 1
Wyjaśnienie: Znak „+” o długości ramienia 0 (0 komórek w każdym kierunku + 1 środek) można utworzyć za pomocą dowolnej cyfry 1.
Wejście: z = [ [0] ]
Wyjście:
Wyjaśnienie: NIE Można utworzyć znak „+”.

[Podejście naiwne] - Rozważ każdy punkt jako środek - O(n^4) czasu i O(n^4) przestrzeni

Przemierzaj komórki macierzy jedna po drugiej. Rozważ każdy przebyty punkt jako środek plusa i znajdź rozmiar +. Dla każdego elementu poruszamy się w lewo i w prawo na dół i do góry. Najgorszy przypadek w tym rozwiązaniu ma miejsce, gdy mamy wszystkie jedynki.

prędkość transmisji w Arduino

[Podejście oczekiwane] — Oblicz wstępnie 4 tablice — O(n^2) czasu i O(n^2) przestrzeni

The pomysł jest utrzymanie czterech macierzy pomocniczych lewy[][] prawy[][] górny[][] dolny[][] do przechowywania kolejnych jedynek w każdym kierunku. Dla każdej komórki (i j) w macierzy wejściowej przechowujemy w nich poniższe informacje cztery macierze -
lewy (i j) przechowuje maksymalną liczbę kolejnych jedynek do lewy komórki (ij), łącznie z komórką (ij).
prawda (i j) przechowuje maksymalną liczbę kolejnych jedynek do Prawidłowy komórki (ij), łącznie z komórką (ij).
góra (i j) przechowuje maksymalną liczbę kolejnych jedynek w szczyt komórki (ij), łącznie z komórką (ij).
dół (i j) przechowuje maksymalną liczbę kolejnych jedynek w spód komórki (ij), łącznie z komórką (ij).

Po obliczeniu wartości dla każdej komórki powyższych macierzy największy'+' zostanie utworzona przez komórkę macierzy wejściowej, która ma maksymalną wartość przy uwzględnieniu minimum ( lewy (i j) prawy (i j) górny (i j) dolny (i j) )

Możemy skorzystać Programowanie dynamiczne aby obliczyć całkowitą liczbę kolejnych jedynek w każdym kierunku:

jeśli mat(i j) == 1
lewy(i j) = lewy(i j - 1) + 1
jeszcze pozostało (i j) = 0

jeśli mat(i j) == 1
góra(i j) = góra(i - 1 j) + 1;
obiekt Java
w przeciwnym razie góra(i j) = 0;

jeśli mat(i j) == 1
dół(i j) = dół (i + 1 j) + 1;
w przeciwnym razie dół(i j) = 0;

jeśli mat(i j) == 1
prawo(ij) = prawo(ij + 1) + 1;
w przeciwnym razie dobrze (i j) = 0;

Poniżej znajduje się implementacja powyższego podejścia:

Java dzieli ciąg znaków według ograniczników

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));

Wyjście

Złożoność czasowa: O(n²) ze względu na cztery przebiegi w celu obliczenia macierzy kierunkowych i jeden końcowy przebieg w celu określenia największego „+”. Każde przejście zajmuje czas O(n²), co prowadzi do ogólnej złożoności O(n²).
Złożoność przestrzeni: O(n²) ze względu na cztery macierze pomocnicze (lewy, prawy, górny, dolny) zużywające O (n²) dodatkowej przestrzeni.