USACO OPEN07 Problem 'solitair' Analysis
by Rob Kolstad
One of the easier ways to visualize the easy solution to this problem
is to work backwards from the goal back to the starting place keeping
track of the best possible sum that can result from a traversal
started from any given square.
Initially, the best (and only) known solution is nothing more than
the value of the 1x1 single square that is the goal square.
An iterative procedure expands the universe of "best" solutions a
little bit at a time. Once the best possible solution for each of
the possible next-possible-traversal squares is known, then a simple
comparison to choose the best way to go yields another "best"
solution square.
By way of example, a 4x4 sample like the problem's description:
8 1 3 1
8 4 12 12
5 9 13 7
10 12 1 2
has a solution (best possible total) matrix that progresses like
this:
? ? ? 1 ? ? 4 1 ? 4 3 1 12 4 3 1
? ? ? ? -> ? ? ? 13 -> ? ? 25 13 -> ? 29 25 13
? ? ? ? ? ? ? ? ? ? ? 20 ? ? 38 20
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 22
Finally, the value in the lower left corner is the best possible
sum. Below is one implementation:
#include <stdio.h>
int layout[7][7];
int bestsum[7][7];
int n;
int cardval[128];
char *cardvals = "A23456789TJQK";
main () {
FILE *fin=fopen("solitair.in","r");
FILE *fout=fopen("solitair.out","w");
char card[5], *p;
int r, c, above, right;
/* make reading easy: */
for (p = cardvals; *p; p++)
cardval[*p] = p-cardvals+1;
/* input: */
fscanf (fin, "%d", &n);
for (r = 0; r < n; r++) {
for (c = 0; c < n; c++) {
fscanf (fin, "%s", card);
layout[r][c] = cardval[ card[0] ];
}
}
/* work backwards to find best sum (upper right of triangle */
bestsum[0][n-1] = layout[0][n-1];
/* upper right of triangle */
for (;;) {
for (c = 0; c < n; c++)
if (bestsum[0][c] != 0) break;
if (c == 0) break;
/* we're one column too far right */
for (c--, r=0; c < n; c++, r++) {
above = 0; if (r > 0) above = bestsum[r-1][c];
right = 0; if (c < n-1) right = bestsum[r][c+1];
/* printf ("working on r=%d c=%d -- above=%d right=%d\n",
r, c, above, right); */
bestsum[r][c] = layout[r][c];
bestsum[r][c] += above > right ? above: right;
}
}
/* lower left of triangle */
while (bestsum[r-1][0] == 0) {
for (r = n; ; r--) /* guaranteed to hit nonzero */
if (bestsum[r][0]) break;
/* we're one row too far up */
for (r++, c=0; r < n; r++, c++) {
above = 0; if (r > 0) above = bestsum[r-1][c];
right = 0; if (c < n-1) right = bestsum[r][c+1];
bestsum[r][c] = layout[r][c];
bestsum[r][c] += above > right ? above: right;
}
}
fprintf (fout, "%d\n", bestsum[r-1][0]);
exit (0);
}
Here's another, much more compact solution from ace Richard Peng.
He exploits starting his indices at 1 instead of 0 by accessing
elements that are initialized to 0:
#include <stdio.h>
#include <string.h>
int v[100][100], n, bes[100][100];
char s[3];
int big (int a, int b) { return (a>b)?a:b; }
main (){
int i,j;
freopen ("solitair.in", "r", stdin);
freopen ("solitair.out", "w", stdout);
scanf("%d",&n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
scanf("%s",s);
v[i][j]= (s[0]=='T')?10: (s[0]=='J')?11:
(s[0]=='Q')?12: (s[0]=='K')?13: (s[0]=='A')?1: (s[0]-'0');
memset (bes, 0, sizeof (bes));
for (i = n; i > 0; i--)
for (j = 1; j <= n; j++)
bes[i][j] = big (bes[i+1][j], bes[i][j-1]) + v[i][j];
printf ("%d\n", bes[1][n]);
return 0;
}