/**
 * PascalTriangleArray is 2D array that store the value of Pascal Triangle.
 * Later, can get the value of routes in grid nxn from PascalTriangleArray[n][n]
 * Reference(s): http://blog.functionalfun.net/2008/07/project-euler-problem-15-city-grids-and.html
 *
 * @author MUHAMMAD AZRI BIN JASNI @ ABDUL RANI
 * @version 04 NOVEMBER 2012
 */
public class solution15
{
    public static void main(String [] args)
    {
        long begin = System.currentTimeMillis();
        int n = 20;
        final int gridSize = n+1;
        long PascalTriangleArray [][];
        PascalTriangleArray = new long[gridSize][gridSize];
        //i for row, j for column

        //set all column 0 to value 1.
        for (int i=0; i<gridSize; i++)
            PascalTriangleArray[i][0] = 1;

        //set all row 0 to value 1.
        for (int j=0; j<gridSize; j++)
            PascalTriangleArray[0][j] = 1;

        //build the rest of PascalTriangleArray
        for (int i=1; i<gridSize; i++)
        {
            for (int j=1; j<gridSize; j++)
            {
                PascalTriangleArray[i][j] = PascalTriangleArray[i][j-1] + PascalTriangleArray[i-1][j] ;
            }
        }

        //display em
        for (int i=0; i<gridSize; i++)
        {
            for (int j=0; j<gridSize; j++)
            {
                System.out.print(PascalTriangleArray[i][j]+ " ");
            }
            System.out.println();
        }

        System.out.println(n+"x"+n+" grid - no of routes: "+PascalTriangleArray[n][n]);
        long end = System.currentTimeMillis();
        System.out.println("Time: "+(end-begin) + "ms");
    }
}