Experienced coders should immediately wonder what the maximum possible answer is, in case they need to use large data types to hold the intermediate values. Opening the dictionary file immediately reveals the somewhat unusual words AA, AAA and AAAA (as well as A). Further examination shows that no word is more than four letters long. This immediately suggests that a grid full of A's is the worst case, in which every trail of up to four letters yields a valid word. If we pick 4 ordered X coordinates and 4 ordered Y coordinates, we will have a slight overestimate of the number of 4-step paths (overestimate because that includes the possibility of using the same square twice). The number of ways of picking 4 ordered but not unique elements from 30 is (30*31*32*33)/(4*3*2*1) = 40920; the number of ways of doing it for X and Y is 40920^2 ~= 1.7e9. The 1, 2 and 3 step paths make little difference, and the total upper bound end up a touch under 1.7 billion (the actual maximum is 1,625,675,650). This is small enough for 32-bit arithmetic (which is obviously faster), but too bit to enumerate the answers one by one.
Since we cannot enumerate the possible answers, we need some form of dynamic programming or other optimisation. Suppose we consider just one word from the dictionary and try to count its occurrences. In the spirit of dynamic programming, let us create small sub-problems that can be used to solve the larger problem: how many times does each prefix occur in each lower-left rectangle of the grid (i.e. those rectangles containing the origin). There are four ways that a prefix P can appear in a rectangle of size (W, H)
Since case 1 is the intersection of cases 2 and 3, the contribution of the first three cases combined is actually S2 + S3 - S1.
These possibilities can be sequenced into a dynamic programming solution for a single word in the dictionary, then placed inside an outer loop over the dictionary.
Here is Coach Anders Kaseorg's solution:
#include <iostream> #include <fstream> #include <string> #include <map> using namespace std; ifstream fin("twalk.in"); ofstream fout("twalk.out"); ifstream fdict("dict.txt"); struct dict { dict() { w = false; for (int i = 0; i < 26; ++i) p[i] = 0; } dict *p[26]; bool w; }; dict d; int x, y, l[30][30]; map<dict *, long long> c[30][30]; long long n = 0; void add (map<dict *, long long> &m, dict *pd, long long nn) { map<dict *, long long>::iterator k = m.find(pd); if (k != m.end()) k->second += nn; else m.insert(make_pair(pd, nn)); if (pd->w) n += nn; } int main() { string s; while (fdict >> s) { dict *pd = &d; for (size_t k = 0; k < s.length(); ++k) { if (!pd->p[s[k] - 'A']) pd->p[s[k] - 'A'] = new dict; pd = pd->p[s[k] - 'A']; } pd->w = true; } fin >> y >> x; for (int j = y - 1; j >= 0; --j) for (int i = 0; i < x; ++i) { char z; fin >> z; l[i][j] = z - 'A'; } for (int j = 0; j < y; ++j) for (int i = 0; i < x; ++i) { if (d.p[l[i][j]]) add(c[i][j], d.p[l[i][j]], 1LL); for (int jj = 0; jj <= j; ++jj) for (int ii = 0; ii <= i; ++ii) if (ii != i || jj != j) for (map<dict *, long long>::const_iterator kk = c[ii][jj].begin(); kk != c[ii][jj].end(); ++kk) if (kk->first->p[l[i][j]]) add(c[i][j], kk->first->p[l[i][j]], kk->second); } fout << n << endl; return 0; }