task154.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Вычисляем максимальный квадрат с правым нижним
// углом в точке (i,j) на основе ужн вычесленного для точки
// (i-1,j-1) . Для этого нам также надо знать сколько
// свободных ячеек левее и выше точки (i,j)

std::pair<int, int> Solve(const vector<string>& a)
{
    vector<vector<int>> r(a.size(),vector<int>(a[0].size(), -1));
    vector<int> v(a[0].size(), -1);
    int m = 0;
    int count = 0;

    for (int i = 0; i < a.size(); ++i) {
        int h = -1;
        for (int j = 0; j < a[0].size(); ++j) {
            if (a[i][j] == '1' || j == 0 || i == 0) {
                auto c = a[i][j] != '1';
                r[i][j] = c;
                h = c ? h : j;
                v[j] = c ? v[j] : i;
                continue;
            }
            auto _a = r[i-1][j-1]+1;
            auto _b = i - v[j];
            auto _c = j - h;

            r[i][j] = min(_a, min(_b, _c));

            if (r[i][j] == m) {
                ++count;
            }

            if (m < r[i][j]) {
                m = r[i][j];
                count = 1;
            }
        }
    }

    return make_pair(m, count);
}


int main() {
    {
        auto r = Solve(
            {
                "100001",
                "010000",
                "100000",
                "001000",
                "000010",
                "001000"
            });
        cout << r.first << " " << r.second << endl;
    }
    {
        auto r = Solve(
            {
                "111111",
                "111111",
                "111111",
                "111111",
                "111111",
                "111111"
            });
        cout << r.first << " " << r.second << endl;
    }
    {
        auto r = Solve(
            {
                "000000",
                "000000",
                "000000",
                "000000",
                "000000",
                "000000"
            });
        cout << r.first << " " << r.second << endl;
    }
    return 0;
}