Максимален плоштад


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон AppDynamics Јаболко Facebook Google IBM, PayPal Twitter
Низа Динамичко програмирање Матрица

Во максималниот квадратен проблем дадовме 2D бинарен матрица исполнет со 0 и 1, пронајдете го најголемиот квадрат што содржи само 1 и вратете ја неговата површина.

пример

влез:

1 0 1 0 0

0 0 1 1 1

1 1 1 1 1

0 0 0 1 0

излез:

4

Приод на брутална сила

Начинот на брутална сила за решавање на овој проблем е да се повтори целата можна квадратна под-матрица и да се избере максимумот од нив.

Програма C ++ за Максимален квадрат

#include <bits/stdc++.h>
using namespace std;
int maximalSquare(vector<vector<char>> &matrix)
{
    int answer = 0;
    int n = matrix.size();
    if (n == 0)
    {
        return 0;
    }
    int m = matrix[0].size();
    if (m == 0)
    {
        return 0;
    }
    for (int sidelength = 1; sidelength <= min(n, m); sidelength++) // sidelength denotes the side length of the sub-matrix
    {
        // i,j are the top left index of the current sub-matrix
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if ((i + sidelength > n) or (j + sidelength > m)) //check if the current sub-matrix is not out of bounds
                {
                    continue;
                }
                bool zero = false;
                // check if this sub matrix contain any zero or not
                for (int x = i; x < i + sidelength; x++)
                {
                    for (int y = j; y < j + sidelength; y++)
                    {
                        if (matrix[x][y] == '0')
                        {
                            zero = true;
                        }
                    }
                }
                if (zero == false) // if this does not contain any zero than this is a valid sub matrix
                {
                    answer = max(answer, sidelength * sidelength);
                }
            }
        }
    }
    return answer;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix[i][j];
        }
    }
    int answer = maximalSquare(matrix);
    cout << answer << endl;
    return 0;
}
4 4
1 0 1 0 
1 0 1 1 
1 1 1 1 
1 0 0 1 
4

Програма JAVA за Максимален квадрат

import java.util.*;
public class Main
{
    public static int maximalSquare(char[][] matrix)
    {
        int answer = 0;
        int n = matrix.length;
        if (n == 0)
        {
            return 0;
        }
        int m = matrix[0].length;
        if (m == 0)
        {
            return 0;
        }
        for (int sidelength = 1; sidelength <= Math.min(n, m); sidelength++) // sidelength denotes the side length of the sub-matrix
        {
            // i,j are the top left index of the current sub-matrix
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if ((i + sidelength > n) || (j + sidelength > m)) //check if the current sub-matrix is not out of bounds
                    {
                        continue;
                    }
                    boolean zero = false;
                    // check if this sub matrix contain any zero or not
                    for (int x = i; x < i + sidelength; x++)
                    {
                        for (int y = j; y < j + sidelength; y++)
                        {
                            if (matrix[x][y] == '0')
                            {
                                zero = true;
                            }
                        }
                    }
                    if (zero == false) // if this does not contain any zero than this is a valid sub matrix
                    {
                        answer = Math.max(answer, sidelength * sidelength);
                    }
                }
            }
        }
        return answer;
    }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                matrix[i][j] = sc.next().charAt(0);
            }
        }
        int answer = maximalSquare(matrix);
    System.out.println(answer);
  }
}



4 5
1 0 1 1 1
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
9

Анализа на сложеност

Временска сложеност

Како што повторуваме над сите плоштади и ќе има приближно N ^ 2 квадрати, така што вкупната сложеност на времето е О (N ^ 4).

Комплексноста на просторот

Бидејќи не сме користеле никаков дополнителен простор, така и просторната комплексност е О (1).

Пристап на динамичко програмирање

Објаснување

Да речеме дека имаме dp низа со големина (n + 1, m + 1) каде dp [i] [j] претставува најголема странична должина на квадрат од сите чиј горен лев агол е I, j.

Значи, ако матрицата [i] [j] е една отколку што можеме да кажеме dp [i] [j] = 1 + мин (dp [i-1], dp [i] [j-1], dp [i-1 ] [j-1]) затоа што најголемиот квадрат од оние со горниот лев агол I, j е само пресек на најголемите квадрати од горниот лев агол (i-1, j), (I, j-1), ( i-1, j-1).

Алгоритам

  1. Иницијализирајте низа dp со големина (n + 1, m + 1) со нули.
  2. Иницијализирајте цел број со нула.
  3. Повторувајте ги сите клетки на матрицата.
    1. Ако матрицата [i] [j] е една од ажурирањето dp [i] [j] = 1 + мин (dp [i-1], dp [i] [j-1], dp [i-1] [j- 1]).
    2. Ажурирај ans = max (ans, dp [i] [j]).
  4. Врати ги анс.

На пример:

Matrix[][]={{‘1’, ‘0’, ‘1’, ‘0’, ‘0’},

{'1', '0', '1', '1', '1'},

{'1', '1', '1', '1', '1'},

{'1', '0', '0', '1', '0'}}

За оваа матрица, низата dp [] [] изгледа вака:

Максимален плоштад

dp [i] [j] ја означува страничната должина на максималниот квадрат од оние чиј горен лев агол има индекс (i, j).

Програма C ++ за Максимален квадрат

#include <bits/stdc++.h>
using namespace std;
int maximalSquare(vector<vector<char>> &matrix)
{
    int n = matrix.size();
    if (n == 0)
    {
        return 0;
    }
    int m = matrix[0].size();
    if (m == 0)
    {
        return 0;
    }
    int ans = 0;
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = n - 1; i >= 0; i--)
    {
        if (matrix[i][m - 1] == '1')
        {
            dp[i][m - 1]++;
            ans = 1;
        }
    }
    for (int i = m - 1; i >= 0; i--)
    {
        if (matrix[n - 1][i] == '1')
        {
            dp[n - 1][i]++;
            ans = 1;
        }
    }
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = m - 2; j >= 0; j--)
        {
            if (matrix[i][j] == '1')
            {
                dp[i][j] = min(dp[i + 1][j + 1], min(dp[i + 1][j], dp[i][j + 1])) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans * ans;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix[i][j];
        }
    }
    int answer = maximalSquare(matrix);
    cout << answer << endl;
    return 0;
}
4 2
1 0 
1 1 
1 1
1 0
4

Програма JAVA за Максимален квадрат

import java.util.*;
public class Main
{
    public static int maximalSquare(char[][] matrix)
    {
        int n = matrix.length;
        if (n == 0)
        {
            return 0;
        }
        int m = matrix[0].length;
        if (m == 0)
        {
            return 0;
        }
        int ans = 0;
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dp[i][j]=0;
            }
        }
        for (int i = n - 1; i >= 0; i--)
        {
            if (matrix[i][m - 1] == '1')
            {
                dp[i][m - 1]++;
                ans = 1;
            }
        }
        for (int i = m - 1; i >= 0; i--)
        {
            if (matrix[n - 1][i] == '1')
            {
                dp[n - 1][i]++;
                ans = 1;
            }
        }
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = m - 2; j >= 0; j--)
            {
                if (matrix[i][j] == '1')
                {
                    dp[i][j] = Math.min(dp[i + 1][j + 1], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans * ans;
    }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                matrix[i][j] = sc.next().charAt(0);
            }
        }
        int answer = maximalSquare(matrix);
    System.out.println(answer);
  }
}
4 5
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
16

Анализа на сложеност

Временска сложеност

Како што повторуваме преку матрицата само еднаш, така е временската сложеност О (N ^ 2).

Комплексноста на просторот

Зедовме низа dp со големина (n + 1, m + 1), така што вселенската комплексност е О (N ^ N).

Референци