ncamaa1

Untitled

Aug 20th, 2016
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. public class Short{
  3.    
  4. public static int shortestPath(int[][] mat)
  5. {
  6.    
  7.     return shortestPath(mat, 0, 0);
  8.    
  9. }
  10.  
  11. // array to work: {{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}}
  12. public static int min(int x,int y){
  13.     return x>y? y:x;
  14.    
  15. }
  16.  
  17. public static int goLeft(int[][]mat, int i, int j, int rows, int cols)
  18. {
  19.     if (i == rows && j == cols)
  20.         return 1;
  21.     if (j>0 && mat[i][j]<mat[i][j-1])
  22.         return 1 + shortestPath(mat, i, j-1);
  23.     return 1000;
  24. }
  25.  
  26. public static int goUp(int[][]mat, int i, int j, int rows, int cols)
  27. {
  28.     if (i == rows && j == cols)
  29.         return 1;
  30.     if (i>0 && mat[i][j]<mat[i-1][j])
  31.         return 1 + shortestPath(mat, i-1, j);
  32.     return 1000;
  33. }
  34.  
  35. public static int goRight(int[][]mat, int i, int j, int rows, int cols)
  36. {
  37.     if (i == rows && j == cols)
  38.         return 1;
  39.     if (j<cols && mat[i][j]<mat[i][j+1])
  40.         return 1 + shortestPath(mat, i, j+1);
  41.     return 1000;
  42. }
  43.  
  44. public static int goDown(int[][]mat, int i, int j, int rows, int cols)
  45. {
  46.     if (i == rows && j == cols)
  47.         return 1;
  48.     if (i<rows && mat[i][j]<mat[i+1][j])
  49.         return 1 + shortestPath(mat, i+1, j);
  50.     return 1000;
  51. }
  52.  
  53. public static int shortestPath(int[][] mat, int i,  int j)
  54. {
  55.     int rows = mat.length-1, cols = mat[0].length-1;
  56.     return min(
  57.                 min (
  58.                         goLeft(mat, i, j, rows, cols)  
  59.                         ,
  60.                         goUp(mat, i, j, rows, cols  )
  61.                     )
  62.                 ,
  63.                 min (  
  64.                         goRight(mat, i, j, rows, cols)
  65.                         ,
  66.                         goDown(mat, i, j, rows, cols )
  67.                        )
  68.               );
  69.              
  70. }
  71. public static void main(String[] args){
  72.     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}};
  73.     System.out.println(shortestPath(mat));
  74. }
  75. }
RAW Paste Data