Grid

By Christopher Xue

The idea is to assign two numbers to each lattice point that represent how many ways we can travel from that point to the end. We need two numbers, one for travelling without making any down moves, and another for travelling with the possibility of making one down move.

We create two matrices to contain these numbers. If we try creating the matrix from (0,0) and progressing recursively from there, we will call the same recursive values over and over again (i.e., both (0,1) and (1,0) rely upon (1,1), forcing us to compute (1,1) twice) and also run into stack overflow error. So instead we start from the end and build from there, until we finally compute the value at (0,0).

We also note that we should compute the matrix of no down moves first, since the second matrix relies upon the first.

For example, if our two matrices are down and noDown, the java code looks like (here we use [x][y] to represent (x,y))

down[x][y] = down[x][y+1] + down[x+1][y] + noDown[x][y-]1

noDown[x][y] = noDown[x][y+1] + noDown[x+1][y]

(we should check for boundary cases; the above is the core of the algorithm)

We also have to remember to assign down[x][y] = 0 and noDown[x][y] = 0 if (x,y) is one of the holes.

Once we create both matrices, we print down[0][0] to obtain the flag, 4294.

Here is a Java solution

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.Math;
import java.util.Scanner;

public class HelloWorld {
    public int[][] a; // can still move down
    public int[][] b; // no down moves
    public int[][] c; // list of holes
    public int m, n;
    public int counter;

    public HelloWorld(int x, int y) {
        m = x;
        n = y;
        counter = 0;
        a = new int[m][n];
        b = new int[m][n];
        c = new int[m][n];
        loadFile("file.txt");
        System.out.println(counter);
    }

    public void loadFile(String fileName) {
        File file = new File(fileName);
        try {
            Scanner inFile = new Scanner(file);
            while (inFile.hasNext()) {
                //System.out.println(point[0] + " " + point[1]);
                c[inFile.nextInt()][inFile.nextInt()] = 1;
                counter++;
            }
            inFile.close();
        } catch (FileNotFoundException e) {
            // e.printStackTrace();
            System.out.println("File is in the wrong directory");
        }
    }

    public void solveB(int x, int y) {
        if (c[x][y] == 1) {
            b[x][y] = 0;
            return;
        }
        if (x != m - 1 && y != n - 1)
            b[x][y] = b[x + 1][y] + b[x][y + 1];
        if (x == m - 1 && y != n - 1)
            b[x][y] = b[x][y + 1];
        if (y == n - 1 && x != m - 1)
            b[x][y] = b[x + 1][y];
        if (x == m - 1 && y == n - 1)
            b[x][y] = 1;
        b[x][y] = b[x][y] % 100000;

    }

    public void solveA(int x, int y) {
        if (c[x][y] == 1) {
            a[x][y] = 0;
            return;
        }

        if (x != m - 1 && y != n - 1)
            a[x][y] = a[x + 1][y] + a[x][y + 1];
        if (x == m - 1 && y != n - 1)
            a[x][y] = a[x][y + 1];
        if (y == n - 1 && x != m - 1)
            a[x][y] = a[x + 1][y];
        if (x == m - 1 && y == n - 1)
            a[x][y] = 1;

        if (y != 0)
            a[x][y] += b[x][y - 1];
        a[x][y] = a[x][y] % 100000;
    }

    public static void main(String[] args) {
        int x = 1000;
        int y = 1500;
        HelloWorld asdf = new HelloWorld(x, y);
        for (int i = x - 1; i >= 0; i--) {
            for (int j = y - 1; j >= 0; j--) {
                asdf.solveB(i, j);
            }
        }
        for (int i = x - 1; i >= 0; i--) {
            for (int j = y - 1; j >= 0; j--) {
                asdf.solveA(i, j);
            }
        }
        System.out.println(asdf.a[0][0]);
    }

}