November 2005 Problem 'numgrid' Analysis

This problem can be solved by a simple exhaustive search. The number of paths is less than 25*4⁵ = 25600 (25 starting points, and up to 4 directions for each hop). The recursive function takes a recursion depth, current position and the number so far, then recurses in each valid direction. [See the solution to 'passwd' for a more in-depth discussion of recursion.]

Somehow the distinct numbers must be counted. One option is a boolean array of 1000000 elements, initialised to false and set to true when a particular element is encountered. Another is to use a C++ or Java set to hold the elements.

Here is topcoder champ Tomek Czajk'a solution:

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <sstream>
using namespace std;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
typedef long long LL;
const int INF = 1000000000; const LL INFLL = LL(INF) * LL(INF);
template<class T> inline int size(const T&c) { return c.size(); }

///////////////////////////////////////////////////////////////////

int tab[5][5];
set<int> seen;

void go(int x,int y,int nr, int v) {
  v = 10*v + tab[x][y];
  ++nr;
  if(nr==6) { seen.insert(v); return; }
  if(x>0) go(x-1,y,nr,v);
  if(x<4) go(x+1,y,nr,v);
  if(y>0) go(x,y-1,nr,v);
  if(y<4) go(x,y+1,nr,v);
}

int main() {
  FILE *f = fopen("numgrid.in","r");
  REP(y,5) REP(x,5) fscanf(f,"%d",&tab[x][y]);
  fclose(f);
  
  REP(x,5) REP(y,5) go(x,y,0,0);
  int res = size(seen);
  
  f = fopen("numgrid.out","w");
  fprintf(f,"%d\n",res);
  fclose(f);
}