میدان حداکثر


سطح دشواری متوسط
اغلب در خشت آمازون AppDynamics سیب فیس بوک گوگل آی بی ام پی پال توییتر
صف برنامه نویسی پویا ماتریس

در مسئله حداکثر مربع یک باینری دو بعدی داده ایم ماتریس با 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 وجود خواهد داشت بنابراین کل پیچیدگی زمان است O (N ^ 4).

پیچیدگی فضا

همانطور که ما از فضای اضافی استفاده نکرده ایم بنابراین پیچیدگی فضا نیز وجود دارد O (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

تحلیل پیچیدگی

پیچیدگی زمانی

همانطور که ما فقط یک بار روی ماتریس تکرار می کنیم بنابراین پیچیدگی زمان است O (N ^ 2).

پیچیدگی فضا

ما یک آرایه dp به اندازه (n + 1 ، m + 1) گرفتیم بنابراین پیچیدگی فضا برابر است O (N ^ N).

منابع