package com.fishercoder.solutions;

/**
 * 576. Out of Boundary Paths
 *
 * There is an m by n grid with a ball.
 * Given the start coordinate (i,j) of the ball,
 * you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right).
 * However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary.
 * The answer may be very large, return it after mod 109 + 7.

 Example 1:

 Input:m = 2, n = 2, N = 2, i = 0, j = 0
 Output: 6
 Explanation:

 Example 2:

 Input:m = 1, n = 3, N = 3, i = 0, j = 1
 Output: 12
 Explanation:

 Note:

 Once you move the ball out of boundary, you cannot move it back.
 The length and height of the grid is in range [1,50].
 N is in range [0,50].

 */
public class _576 {

    /**reference: https://leetcode.com/articles/out-of-boundary-paths/#approach-2-recursion-with-memoization-accepted*/
    public int findPaths(int m, int n, int N, int x, int y) {
        int M = 1000000000 + 7;
        int[][] dp = new int[m][n];
        dp[x][y] = 1;
        int count = 0;
        for (int moves = 1; moves <= N; moves++) {
            int[][] temp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == m - 1) {
                        count = (count + dp[i][j]) % M;
                    }
                    if (j == n - 1) {
                        count = (count + dp[i][j]) % M;
                    }
                    if (i == 0) {
                        count = (count + dp[i][j]) % M;
                    }
                    if (j == 0) {
                        count = (count + dp[i][j]) % M;
                    }
                    temp[i][j] = (((i > 0 ? dp[i - 1][j] : 0) + (i < m - 1 ? dp[i + 1][j] : 0)) % M
                           + ((j > 0 ? dp[i][j - 1] : 0) + (j < n - 1 ? dp[i][j + 1] : 0)) % M) % M;
                }
            }
            dp = temp;
        }
        return count;
    }

}

@@ -783,16 +783,67 @@
 6 %7B%0A
-%0A    /**
+    public static class Solution1 %7B%0A        /**%0A         * 
 refe
@@ -948,19 +948,33 @@
 accepted
-*/%0A
+%0A         */%0A    
     publ
@@ -1023,24 +1023,28 @@
 x, int y) %7B%0A
+    
         int 
@@ -1063,32 +1063,36 @@
 00 + 7;%0A        
+    
 int%5B%5D%5B%5D dp = new
@@ -1111,16 +1111,20 @@
         
+    
 dp%5Bx%5D%5By%5D
@@ -1129,16 +1129,20 @@
 y%5D = 1;%0A
+    
         
@@ -1156,32 +1156,36 @@
 nt = 0;%0A        
+    
 for (int moves =
@@ -1215,32 +1215,36 @@
 ) %7B%0A            
+    
 int%5B%5D%5B%5D temp = n
@@ -1261,32 +1261,36 @@
 n%5D;%0A            
+   
+ 
 for (int i = 0; 
@@ -1299,24 +1299,28 @@
 %3C m; i++) %7B%0A
+    
             
@@ -1365,32 +1365,36 @@
                 
+    
 if (i == m - 1) 
@@ -1411,32 +1411,36 @@
                 
+   
+ 
 count = (count +
@@ -1467,34 +1467,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1539,32 +1539,36 @@
                 
+  
+  
 count = (count +
@@ -1595,34 +1595,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1663,32 +1663,36 @@
                 
+  
+  
 count = (count +
@@ -1719,34 +1719,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1787,32 +1787,36 @@
                 
+ 
+   
 count = (count +
@@ -1843,34 +1843,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1988,16 +1988,21 @@
         
+ 
+    
 + ((j %3E 
@@ -2075,34 +2075,41 @@
                 
-%7D%0A
+    %7D%0A   
             %7D%0A  
@@ -2096,34 +2096,39 @@
 %0A               
+ 
 %7D%0A
+    
             dp =
@@ -2142,26 +2142,33 @@
         
-%7D%0A
+    %7D%0A   
         
 return c
@@ -2159,16 +2159,17 @@
         
+ 
 return c
@@ -2174,16 +2174,26 @@
  count;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 576