Method prince.This should be recursive method without any loops.Prince can move only one cell to the west or east or south or north(not diagonally). Prince is jumping by the roofs, searching for the villain.The cell with a villain values -1, and this is the only negative value in the array. Method takes three parameters: drm - Digital Rood Map(as 2d array), i - rows, j - columns (This is the index where he starts his path). Cells value represents the roof height. Prince can jump from one roof to another under these circumstances:

1. If the roof that he jumps on is the same value,as the roof that he jumps from.
2. If the difference between roof that he jumps down from to the roof that lays above is not more than 2. (from 5 to 3, or from 2 to 0).
3. Prince can climb up to another roof if its not more than 1 cell above. (from 3 to 4, or from 0 to 1). Method must return the shortest way to the villain(to the index that values -1). If prince deadlocks, then method should return -1.

    public class Test {
    public static int prince(int[][] drm, int i, int j) {
        final int BEEN_HERE = Integer.MAX_VALUE;
        if (drm[i][j] == -1) {
            return 1;
        }
        int temp  = drm[i][j];
        drm[i][j] = BEEN_HERE;
        int north = Integer.MAX_VALUE, south = Integer.MAX_VALUE, east = Integer.MAX_VALUE, west = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            if(drm[i - 1][j]==temp||temp - drm[i-1][j]==2||Math.abs(temp - drm[i-1][j])==1 || drm[i-1][j]==-1)
                north = prince(drm, i - 1, j)   1;
        }
        if (i   1 < drm[0].length) {
            if(drm[i   1][j]==temp||temp - drm[i   1][j]==2||Math.abs(temp - drm[i   1][j])==1 || drm[i   1][j]==-1)
                south = prince(drm, i   1, j)   1;
        }
        if (j - 1 >= 0 ) {
            if(temp==drm[i][j-1] || temp - drm[i][j-1]==2||Math.abs(temp - drm[i][j-1])==1 || drm[i][j-1]==-1)
                west = prince(drm, i, j - 1)   1;
        }
        if (j   1 < drm.length) {
            if(temp==drm[i][j 1] || temp - drm[i][j 1]==2||Math.abs(temp - drm[i][j 1])==1 || drm[i][j 1]==-1)
                east = prince(drm, i, j   1)   1;
        }
        if(north==Integer.MAX_VALUE&&south==Integer.MAX_VALUE&&east==Integer.MAX_VALUE&&west==Integer.MAX_VALUE){
            return -1;
        }
        return Math.min(Math.min(north, south), Math.min(east, west));
    }
    public static void main(String[] args) {
        int[][] a = 
        {{2,0,1,2,3}
        ,{2,3,5,5,4},
         {8,-1,6,8,7},
         {3,4,7,2,4}
        ,{2,4,3,1,2}};
        System.out.println(prince(a, 4, 4));
    }
}

From the index a[4][4] when the prince deadlocks method returns 1 instead of -1. Can you please help me with any idea how can i prevent this.

 int[][] a = 
        {{2,0,1,2,3}
        ,{2,3,5,5,4},
         {8,-1,6,8,7},
         {3,4,7,2,4}
        ,{2,4,3,1,2}};
        System.out.println(prince(a, 4, 4));

CodePudding user response：

I have added another parameter steps to the function signature, the problem was that you returned the path length even to invalid paths. But the function should return the path length only when path is valid, else return MAX_VALUE

public static int prince(int[][] drm, int i, int j,int steps) {
    final int BEEN_HERE = Integer.MAX_VALUE;
    if (drm[i][j] == -1) {
        return steps;
    }
    int temp  = drm[i][j];
    drm[i][j] = BEEN_HERE;
    int north = Integer.MAX_VALUE, south = Integer.MAX_VALUE, east = Integer.MAX_VALUE, west = Integer.MAX_VALUE;
    if (i - 1 >= 0) {
        if(drm[i - 1][j]==temp||temp - drm[i-1][j]==2||Math.abs(temp - drm[i-1][j])==1 || drm[i-1][j]==-1)
            north = prince(drm, i - 1, j,steps 1);
    }
    if (i   1 < drm[0].length) {
        if(drm[i   1][j]==temp||temp - drm[i   1][j]==2||Math.abs(temp - drm[i   1][j])==1 || drm[i   1][j]==-1)
            south = prince(drm, i   1, j,steps 1);
    }
    if (j - 1 >= 0 ) {
        if(temp==drm[i][j-1] || temp - drm[i][j-1]==2||Math.abs(temp - drm[i][j-1])==1 || drm[i][j-1]==-1)
            west = prince(drm, i, j - 1,steps 1);
    }
    if (j   1 < drm.length) {
        if(temp==drm[i][j 1] || temp - drm[i][j 1]==2||Math.abs(temp - drm[i][j 1])==1 || drm[i][j 1]==-1)
            east = prince(drm, i, j   1,steps 1) ;
    }
    drm[i][j]=temp;
    return Math.min(Math.min(north, south), Math.min(east, west));
}
 public static int prince(int[][] drm, int i, int j) {
     int res= prince(drm,i,j,1);
     if(res==Integer.MAX_VALUE)
     return -1;
     else return res;
}
public static void main(String[] args) {
     int[][] a = 
    {{2,0,1,2,3}
    ,{2,3,5,5,4},
     {8,-1,6,8,7},
     {3,4,7,2,4}
    ,{2,4,3,1,2}};
    System.out.println(prince(a, 0, 0));
}