Easy Maze Problem

Alice challenges Bob to cross her Maze. 

The Maze is in the form of a rectangular grid. where there are M+1 levels numbered from 0-M and each level has N+1  doors numbered from 0 - N, all the doors lead to the same upper level.

Alice is confident that she doesn’t need to add any traps to the maze and Bob is still going to fail to cross it. Each door of level  ‘i’ leads to the next level 'i+1' and it is possible to travel vertically at the current level without restrictions. 

But Bob is a cautious guy, and he suspects some of the doors must be trapped. So he has formulated a plan to cross the Maze, his plan is an array of Integers C, which tells him which possible doors he can choose at each level. At each level i where 1 <=i<=M C[i] denotes the absolute difference between Bob’s previous choice of the door (the door through which he entered the current level) and the current door that he can take. Eg, if he took door 5 at level i-1, and C[i] is 4, then he must take either door number 5+4 = 9  or  5-4= 1, at this level. He can never go outside the grid.  

Bob always chooses his lucky number Bth Door when he enters the Maze at level 0.

Count and print the number of doors from which Bob can possibly exit the Maze at the Mth level, or print -1 if it impossible for Bob to exit given his current plan. 

Example:

Input: 4 4
0
2 1 2 1
Output: 3

Approach

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class EasyMazeProblem {
    public static void main(String args[]) throws Exception {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = inp.readLine().split(" ");
        int row = Integer.parseInt(s1[1]);
        int colomn = Integer.parseInt(s1[0]);

        row++;
        colomn++;
        int at = Integer.parseInt(inp.readLine());
        boolean[][] dp = new boolean[row][colomn];
        int[] given = new int[row - 1];
        s1 = inp.readLine().split(" ");
        for (int i = 0; i < row - 1; i++) {
            given[i] = Integer.parseInt(s1[i]);
        }

        dp[0][at] = true;

        for (int i = 0; i < row - 1; i++) {
            for (int j = 0; j < colomn; j++) {
                if (dp[i][j]) {
                    int a = given[i];
                    int l = j - a;
                    int r = j + a;

                    if (l >= 0) {
                        dp[i + 1][l] = true;
                    }
                    if (r < colomn) {
                        dp[i + 1][r] = true;
                    }
                }
            }
        }

        int ans = -1;

        for (int i = 0; i < colomn; i++) {
            if (dp[row - 1][i]) {
                if (ans < 0) {
                    ans = 1;
                } else {
                    ans++;
                }
            }
        }
        System.out.println(ans);

    }

    public static long calc(int a, int b) {
        long c = b - a + 1;
        c = c * (c + 1);
        c /= 2l;
        return c;
    }

}