Prob15

public class Problem15 {

    public static void main(String[] args) {
        //long startTime = System.currentTimeMillis();
        System.out.println(lattice(20));
        //double elapseTime = (double)(System.currentTimeMillis() - startTime)/1000.0;
        //System.out.println(elapseTime);
    }

    static long lattice(int size){
        long[][] lattice = new long[size+1][size+1];
        boolean firstIteration = true;

        for(int i = 0; i<=size;i++)
            lattice[0][i] = 1;

        for(int y = 1; y<=size;y++){
            firstIteration = true;
            for(int x = y; x <=size; x++){
                if(firstIteration) {
                    lattice[y][x] = lattice[y-1][x] *2;
                    firstIteration = false;
                }else {
                    lattice[y][x] = lattice[y][x-1] + lattice[y-1][x];
                }
            }
        }
        return lattice[size][size];
    }

    @Deprecated
    static long latticeRecurse(int size, int dir, int step, long counter){
        if (step == size*2 && dir == 0)
            return counter+1;

        if ( dir < size && step < size*2 && ((step+1)*(dir+1)) <= (size*size) )
            counter = latticeRecurse(size,dir+1,step+1,counter);

        if( dir > -size && step < size*2 && ((step+1)*(dir-1)) >= -(size*size) )
            counter = latticeRecurse(size,dir-1,step+1,counter);

        return counter;
    }
}