AcWing 1612. Java求解,一个小技巧取消边界判断
原题链接
中等
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt(),m=scanner.nextInt();
//从1开始可以取消边界判断
int[][] matrix=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
matrix[i][j]=scanner.nextInt();
}
}
int res=getMaxSquare(matrix);
System.out.println(res);
}
public static int getMaxSquare(int[][] matrix){
int row=matrix.length,col=matrix[0].length,res=0;
int[][] dp=new int[row][col];
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
if(matrix[i][j]==1){
//当前以(i,j)为右下角的最大正方形边长。需要判断左边、上边、左上边并取最小边长。
dp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
res=Math.max(res,dp[i][j]);
}
}
}
return res*res;
}
}