package com.company;

import sun.security.util.BigInt;

import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        boolean[][] grid =
                {
                        {true, true, true, true},
                        {false, true, true, true},
                        {true, false, true, true},
                        {true, true, true, true},
                };

        Boolean[][] memo = new Boolean[4][4];
        boolean path = findPath(grid, 3, 3, memo);// 0,0; 0,1; 0,2; 1,2;
        System.out.println(path);
    }

    public static boolean findPath(boolean[][] grid, int endRow, int endColumn, Boolean[][] memo) {
        if (endRow == 0 && endColumn == 0) {
            return true;
        } else if (grid[endRow][endColumn]) {
            boolean pathUp = false;
            boolean pathLeft = false;
            if (endColumn - 1 >= 0) {
                if (memo[endRow][endColumn - 1] != null) {
                    pathUp = memo[endRow][endColumn - 1];
                } else {
                    pathUp = findPath(grid, endRow, endColumn - 1, memo);
                }
            }
            if (endRow - 1 >= 0) {
                if (memo[endRow - 1][endColumn] != null) {
                    pathLeft = memo[endRow - 1][endColumn];
                } else {
                    pathLeft = findPath(grid, endRow - 1, endColumn, memo);
                }
            }

            memo[endRow][endColumn] = pathLeft || pathUp;

            return pathLeft || pathUp;
        }
        return false;
    }


}