15. Grid Routes

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

import java.math.BigInteger;
public class Problem15 {
    public void routes() {
        int n=20;
        BigInteger n2f = factorial(2*n);
        BigInteger n1f = factorial(n);
        BigInteger line  = n2f.divide((n1f.multiply(n1f)));
        System.out.println(line);
    }

    public BigInteger factorial(int n) {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }

    public static void main(String[] args) {
        Problem15 p = new Problem15();
        p.routes();
    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: