Hi community, I've come across this problem: https://www.geeksforgeeks.org/problems/find-shortest-safe-route-in-a-matrix/1

Below is my AC Java solution

Issue: This code must not be AC according to me.

I have memoized the results, dp[i][j] = length of shortest path from i,j to reach the last col but here we're reaching i,j through different paths and the cells which could be further visited starting from i,j depend upon the cells already visited in the current path, hence dp[i][j] should be different when we reach i,j through different paths, hence we cannot memoize its result

Please correct me if I'm wrong,

private static int[] DI = {-1,1,0,0};
private static int[] DJ = {0,0,-1,1};
private boolean isInMat(int i, int j, int n, int m) {
    return 0<=i && i<n && 0<=j && j<m;
}

int[][] dp;

int dfs(int i, int j, int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    
    if(j == m-1) return 1;
    if(dp[i][j] != -1) return dp[i][j];
    
    mat[i][j] = 0;
    
    int ans = Integer.MAX_VALUE;
    for(int a=0; a<4; a++) {
        int ni = i+DI[a];
        int nj = j+DJ[a];
        if(!isInMat(ni, nj, n, m)) continue;
        if(mat[ni][nj] != 1) continue;
        ans = Math.min(ans, dfs(ni, nj, mat));
    }
    
    mat[i][j] = 1;
    return dp[i][j] =  (ans == Integer.MAX_VALUE ? ans : 1+ans);
}

public int findShortestPath(int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    dp = new int[n][m];
    for(int i=0; i<n; i++) Arrays.fill(dp[i],-1);
    
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++) {
        if(mat[i][j] != 0) continue;
        for(int a=0; a<4; a++) {
            int ni = i+DI[a];
            int nj = j+DJ[a];
            if(isInMat(ni, nj, n, m) && mat[ni][nj] == 1)
            mat[ni][nj] = -1;
        }
    }
    
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
    if(mat[i][j] == -1) mat[i][j] = 0;
    
    int ans = Integer.MAX_VALUE;
    for(int i=0; i<n; i++) {
        if(mat[i][0] == 1)
        ans = Math.min(ans, dfs(i, 0, mat));
    }
    
    return ans == Integer.MAX_VALUE ? -1 : ans;
}