[CareerCup] 18.11 Maximum Subsquare 最大子方形

class Subsquare {
public:
    int row, col, size;
    Subsquare(int r, int c, int sz): row(r), col(c), size(sz) {}
    void print() {
        cout << "(" << row << ", " << col << ", " << size << ")" << endl;
    }
};

bool is_square(vector<vector<int>> &matrix, int row, int col, int size) {
    for (int j = 0; j < size; ++j) {
        if (matrix[row][col + j] == 1) return false;
        if (matrix[row + size - 1][col + j] == 1) return false;
    }
    for (int i = 1; i < size - 1; ++i) {
        if (matrix[row + i][col] == 1) return false;
        if (matrix[row + i][col + size - 1] == 1) return false;
    }
    return true;
}

Subsquare* find_square_with_size(vector<vector<int>> &matrix, int squareSize) {
    int cnt = matrix.size() - squareSize + 1;
    for (int row = 0; row < cnt; ++row) {
        for (int col = 0; col < cnt; ++col) {
            if (is_square(matrix, row, col, squareSize)) {
                return new Subsquare(row, col, squareSize);
            }
        }
    }
    return NULL;
}

Subsquare* find_square(vector<vector<int>> &matrix) {
    for (int i = matrix.size(); i >= 1; --i) {
        Subsquare *square = find_square_with_size(matrix, i);
        if (square) return square;
    }
    return NULL;
}

class Subsquare {
public:
    int row, col, size;
    Subsquare(int r, int c, int sz): row(r), col(c), size(sz) {}
    void print() {
        cout << "(" << row << ", " << col << ", " << size << ")" << endl;
    }
};

class SquareCell {
public:
    int zerosRight = 0, zerosBelow = 0;
    SquareCell(int right, int below): zerosRight(right), zerosBelow(below){}
    void setZerosRight(int right) {
        zerosRight = right;
    }
    void setZerosBelow(int below) {
        zerosBelow = below;
    }
};

bool is_square(vector<vector<SquareCell*>> &matrix, int row, int col, int size) {
    SquareCell *topLeft = matrix[row][col];
    SquareCell *topRight = matrix[row][col + size - 1];
    SquareCell *bottomRight = matrix[row + size - 1][col];
    if (topLeft->zerosRight < size) return false;
    if (topLeft->zerosBelow < size) return false;
    if (topRight->zerosBelow < size) return false;
    if (bottomRight->zerosRight < size) return false;
    return true;
}

vector<vector<SquareCell*>> process_square(vector<vector<int>> &matrix) {
    vector<vector<SquareCell*>> res(matrix.size(), vector<SquareCell*>(matrix.size()));
    for (int r = matrix.size() - 1; r >= 0; --r) {
        for (int c = matrix.size() - 1; c >= 0; --c) {
            int rightZeros = 0, belowZeros = 0;
            if (matrix[r][c] == 0) {
                ++rightZeros;
                ++belowZeros;
                if (c + 1 < matrix.size()) {
                    SquareCell *pre = res[r][c + 1];
                    rightZeros += pre->zerosRight;
                }
                if (r + 1 < matrix.size()) {
                    SquareCell *pre = res[r + 1][c];
                    belowZeros += pre->zerosBelow;
                }
            }
            res[r][c] = new SquareCell(rightZeros, belowZeros);
        }
    }
    return res;
}

Subsquare* find_square_with_size(vector<vector<SquareCell*>> &processed, int square_size) {
    int cnt = processed.size() - square_size + 1;
    for (int row = 0; row < cnt; ++row) {
        for (int col = 0; col < cnt; ++col) {
            if (is_square(processed, row, col, square_size)) {
                return new Subsquare(row, col, square_size);
            }
        }
    }
    return NULL;
}

Subsquare* find_square(vector<vector<int>> &matrix) {
    vector<vector<SquareCell*>> processed = process_square(matrix);
    // cout << "here" << endl;
    for (int i = matrix.size(); i >= 1; --i) {
        Subsquare *square = find_square_with_size(processed, i);
        if (square) return square;
    }
    return NULL;
}