# 最大平方

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 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
{
}
}
}
}
}
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];
}
}
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 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
{
}
}
}
}
}
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);
}
}
}
}

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

## 动态规划方法

### 算法

1. 用零初始化大小为（n + 1，m + 1）的dp数组。
2. 用零初始化整数ans。
3. 遍历矩阵的所有单元。
1. 如果矩阵[i] [j]比更新dp [i] [j] = 1 + min（dp [i-1]，dp [i] [j-1]，dp [i-1] [j- 1]）。
2. 更新ans = max（ans，dp [i] [j]）。
4. 返回ans。

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

{'1'，'0'，'1'，'1'，'1'}，

{'1'，'1'，'1'，'1'，'1'}，

{'1'，'0'，'0'，'1'，'0'}}

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];
}
}
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);
}
}
}
}
```
```4 5
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
```
`16`