USACO OPEN09 Problem 'goodgrs' Analysis

by Rob Kolstad

This task's solution is brute-force: calculate the sum of all possible 3 x 3 squares.

The solution below uses a pair of for loops to locate the upper left corner of the 3 x 3 square and then another pair of lops to to do the actual summing. The code should be clear.

#include <stdio.h>
#include <stdlib.h>

int pasture[100+4][100+4];

int main() {
    FILE *fin = fopen("goodgrs.in","r");
    FILE *fout = fopen("goodgrs.out", "w");
    int nr, nc, r, c, r1, c1;
    int bestsum = -1, bestr, bestc, sum;
    fscanf (fin, "%d %d", &nr, &nc);
    for (r = 1; r <= nr; r++)
        for (c = 1; c <= nc; c++)
            fscanf (fin, "%d", &pasture[r][c]);

        /* upper left corner r,c */
    for (r = 1; r <= nr; r++) {
        for (c = 1; c <= nc; c++) {
            sum = 0;
                        /* sum the square: */
            for (r1 = r; r1 < r + 3; r1++)
                for (c1 = c; c1 < c + 3; c1++)
                    sum += pasture[r1][c1];
            if (sum > bestsum) {
                bestsum = sum;
                bestr = r;
                bestc = c;
            }
        }
    }
    fprintf (fout, "%d\n%d %d\n", bestsum, bestr, bestc);
    exit (0);
}