USACO 3.3 Home On The Range

Another relatively straightforward DP problem: the basic idea is to calculate the maximum possible squares (land segment that cows can graze on) that each land can expand to, if the given land is considered as the top-left most corner of the square land segment to be expanded. We calculate this information for each land, starting from the right-down most land (which is just itself), then iteratively repeat the calculation until we reach the top-left most corner. During the computation we can also calculate the final answer incrementally.

#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
vector<vector<int>> dp;
vector<int> ret;

int main() {
    ifstream fin("range.in");
    ofstream fout("range.out");

    fin >> N;
    dp = vector<vector<int>>(N, vector<int>(N, 0));
    ret = vector<int>(N + 1, 0);

    char c;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            fin >> c;
            dp[i][j] = c - '0';
        }
    }

    for (int i = N - 2; i >= 0; --i) {
        for (int j = N - 2; j >= 0; --j) {
            if (!dp[i][j]) continue;
            dp[i][j] = std::min(std::min(dp[i][j + 1], dp[i + 1][j]),
                                dp[i + 1][j + 1]) + 1;
            for (int k = 2; k <= dp[i][j]; ++k) {
                ret[k]++;
            }
        }
    }

    for (int i = 2; i < N + 1; ++i) {
        if (!ret[i]) continue;
        cout << i << " " << ret[i] << endl;
        fout << i << " " << ret[i] << endl;
    }
}