1139. 最大的以 1 为边界的正方形

1139. 最大的以 1 为边界的正方形

1.想法:

1.循环暴力

循环遍历每个节点的值,当当前值为1的时候向左右扩散能找到的最大的边长

我们存在两个问题
1.怎么确定最大边长
2.怎么确定这个最大边长所构成的正方形是合法的
对于第一个问题:我们可以从改点到行边界和竖边界找到最大的边长,如果不合法依次减一直到为0
对于第二个问题:我们可以以改点为左上顶点依次检测每个边是否合法

例如:对于点(1,0) image.png
向右扩散到最右,向下边找到最大边长的上界.可以找到最大边长为min(向右,向下)
然后再去判断每条边是否合法
image.png

2.动态规划

//TODO

2.代码

class Solution {
   public int largest1BorderedSquare(int[][] grid) {
        int row = grid.length,col = grid[0].length,endX=0,endY=0,maxSide=0;
         for(int i=0;i<row;i++){
             for(int j=0;j<col;j++){
                 if(grid[i][j] == 1){
                     int disX = row-i;
                     int disY = col-j;
                     int side = disX>disY?disY:disX;
                     while(side>maxSide){
                         endX = i+side-1;
                         endY = j+side-1;
                         if(checkroute(grid,i,j,endX,endY)){
                             maxSide = side;
                             break;
                         }else{
                             side--;
                         }
                     }

                 }
             }
         }
         return maxSide*maxSide;
    }

    private boolean checkroute(int[][] grid, int startX, int startY, int endX, int endY) {
        //检测上左
        int left = startX;
        while(left<=endX){
            if(grid[left++][startY]!=1)return false;
        }
        //检测左下
        int leftDown = startY;
        while(leftDown<=endY){
            if(grid[startX][leftDown++]!=1)return false;
        }
        //检测右下
        int rightDown = startY;
        while(rightDown<=endY){
            if(grid[endX][rightDown++]!=1)return false;
        }
        //检测下左
        int downLeft = startX;
        while(downLeft<=endX){
            if(grid[downLeft++][endY]!=1)return false;
        }
        return true;
    }
}