boundry.java

// import java.util.Arrays;

// class boundry {
//     static int[][][] dp = new int[60][60][60];
//     static int mod = 1000000009;
//     public static void main(String[] args) {
//         int  m = 2, n = 3, maxMove = 8, startRow = 1, startColumn = 0;
//         System.out.println(findPaths(m, n, maxMove, startRow, startColumn));
//     }

//     public  static int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
//         int ans = 0;
//         for (int[][] row : dp) {
//             for (int[] is : row) {

//                 Arrays.fill(is, -1);
//             }
//         }
//         return dfs(startRow, startColumn, maxMove, m, n, 0);

//     }

//     private static  int dfs(int r, int c, int maxMove, int m, int n, int count) {

//         if (r >= m || c >= n || r < 0 || c < 0) {

//             return 1;
//         }
//         if (maxMove == 0)
//             return 0;

//         if (dp[r][c][maxMove] != -1)
//             return dp[r][c][maxMove];

//         int left = dfs(r, c - 1, maxMove - 1, m, n, count);
//         int right = dfs(r, c + 1, maxMove - 1, m, n, count);
//         int up = dfs(r - 1, c, maxMove - 1, m, n, count);
//         int down = dfs(r + 1, c, maxMove - 1, m, n, count);

//         int total = (left + right + up + down) % mod;
//         dp[r][c][maxMove]=total;
          
//         return dp[r][c][maxMove];

//     }

// }