题解 | #最大正方形#

没人暴力，我来暴力

遍历二维数组的每一个结点

如果结点值为0则跳过

如果结点值为1，则进行广搜

判断当前结点的右结点，下结点，右下结点是否也都是1，

如果是则将这三个结点入队，边长++，然后将边长的平方与当前最大面积进行比较，并进行下一步广搜

如果不是，则直接返回

#include <climits>
class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int maxn = 0;
    bool is_valid(vector<vector<char> >& matrix,int i,int j){               //查看当前结点的右节点，下节点，右下结点是否合法
        bool flag = true;
        if(i+1 >= matrix.size()){
            flag = false;
        }else if(j+1 >= matrix[i].size()){
            flag = false;
        }else{
            if(matrix[i+1][j] == '0' || matrix[i][j+1] == '0' || matrix[i+1][j+1] == '0'){
                flag = false;
            }
        }
        return flag;
    }
    int biggest(vector<vector<char> >& matrix,int i,int j){                 //查看以i，j为左上角的正方形的面积
        int now = 1;
        deque<pair<int,int>> q;
        deque<pair<int,int>> tq;
        bool flag = true;
        q.push_back(pair<int,int>(i,j));
        while((!q.empty()) && flag){                                        //广搜
           pair<int,int> temp;
           while(!q.empty()){
                temp = q.front();
                q.pop_front();
                if(is_valid(matrix, temp.first, temp.second)){              //如果当前结点的下一步合法，则将右、下和右下结点入队
                    tq.push_back(pair<int,int>(temp.first+1,temp.second));
                    tq.push_back(pair<int,int>(temp.first,temp.second+1));
                    tq.push_back(pair<int,int>(temp.first+1,temp.second+1));                    
                }else{
                    flag =false;
                }
            }
            if(flag == true){
                now++;
            }
            while(!tq.empty()){
                temp = tq.front();
                tq.pop_front();
                q.push_back(temp);
            }
        }
        if(now*now > maxn){
            maxn = now*now;
        }
        return now;
    }
    int solve(vector<vector<char> >& matrix) {
        // write code here
        int answer = 0;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[i].size(); j++){
                if(matrix[i][j] == '1'){
                    biggest(matrix,i,j);
                }
            }
        }
        answer = maxn;
        return answer;
    }
};