Hello to all . I solve one problem and cannot solve it. Help is needed. So:

There is a two-dimensional array. It is necessary to find the shortest path from (0,0) To the right lower end for example (4,4). The path through [1,1] [2,2] and so on is forbidden. The diagonal path is forbidden. At the end I should output the shortest path. In our case, it will print "10." Stop putting down cons. enter image description here

Developments:

public class moed2AQuation12015

{

 public static void main (String args[]){ int mat [][] = {{ 3,13,15,28,30}, { 40,51,52,29,30}, { 28,10,53,54,53}, { 53,12,55,53,60}, { 70,62,56,20,80}, { 80,81,90,95,100}}; System.out.println(" " + shortestPath(mat)); } public static int shortestPath (int [][] mat){ return shortestPath (mat,0,0,0,0,1); } public static int shortestPath (int [][] mat,int x,int y,int x1, int y1,int count){ x1 = mat.length -1; y1 = mat[0].length -1; if (x > x1 || y > y1) return 0; if ( x == mat.length && y == mat[0].length ) return 1; System.out.println(" -> " + mat[x][y] + " --> " + count); count = shortestPath(mat,x+1,y,x1,y1,count +1) + shortestPath(mat,x,y+1,x1,y1,count +1); return 0; }

}

  • 2
    Is it possible to complete the condition? In this form, everything is very simple, in general, it is solved by searching in width ... - pavel
  • The answer is good. But this is not what they want from me in the exam. If I write: arr.length + arr [0] .length -1 ... Then I get 5 points out of 25. - Yosef Gorbov
  • @YosefGorbov: I think you think that we should write you an answer in such a way that your teacher likes it. - VladD
  • No, give solutions for all cases. - Yosef Gorbov
  • I already found. Thank you all very much. - Yosef Gorbov

1 answer 1

 public class pathFinder { public static void main (String args[]){ int mat [][] = {{ 3,13,15,28,30}, { 40,51,52,29,30}, { 28,10,53,54,53}, { 53,12,55,53,60}, { 70,62,56,20,80}, { 80,81,90,95,100}}; System.out.println (shorterPath(mat)); } public static int shorterPath(int[][]mat) { return shorterPath(mat,0,0,0,0); } public static int shorterPath(int[][]mat,int i,int j,int counter,int preval) { if(!isValid(mat,i,j)|| preval >= mat[i][j]) return mat.length*mat[0].length*2; if (i==mat.length-1 && j== mat[0].length-1) { counter++; return counter; } else { int a=shorterPath(mat,i+1,j,counter+1,mat[i][j]); int b=shorterPath(mat,i-1,j,counter+1,mat[i][j]); int c=shorterPath(mat,i,j+1,counter+1,mat[i][j]); int d=shorterPath(mat,i,j-1,counter+1,mat[i][j]); if(a<=b && a<=c && a<=d) return a; if(b<=a && b<=c && b<=d) return b; if(c<=a && c<=b && c<=d) return c; return d; } } public static boolean isValid(int[][]a,int i,int j) { if(i>=0 && i<=a.length-1 && j>=0 && j<= a[0].length-1) return true; else return false; }

}