public class Short{

public static int shortestPath(int[][] mat)
{

    return shortestPath(mat, 0, 0);

}

// 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}}
public static int min(int x,int y){
    return x>y? y:x;

}

public static int goLeft(int[][]mat, int i, int j, int rows, int cols)
{
    if (i == rows && j == cols)
        return 1;
    if (j>0 && mat[i][j]<mat[i][j-1])
        return 1 + shortestPath(mat, i, j-1);
    return 1000;
}

public static int goUp(int[][]mat, int i, int j, int rows, int cols)
{
    if (i == rows && j == cols)
        return 1;
    if (i>0 && mat[i][j]<mat[i-1][j])
        return 1 + shortestPath(mat, i-1, j);
    return 1000;
}

public static int goRight(int[][]mat, int i, int j, int rows, int cols)
{
    if (i == rows && j == cols)
        return 1;
    if (j<cols && mat[i][j]<mat[i][j+1])
        return 1 + shortestPath(mat, i, j+1);
    return 1000;
}

public static int goDown(int[][]mat, int i, int j, int rows, int cols)
{
    if (i == rows && j == cols)
        return 1;
    if (i<rows && mat[i][j]<mat[i+1][j])
        return 1 + shortestPath(mat, i+1, j);
    return 1000;
}

public static int shortestPath(int[][] mat, int i,  int j)
{
    int rows = mat.length-1, cols = mat[0].length-1;
    return min(
                min (
                        goLeft(mat, i, j, rows, cols)
                        ,
                        goUp(mat, i, j, rows, cols  )
                    )
                ,
                min (
                        goRight(mat, i, j, rows, cols)
                        ,
                        goDown(mat, i, j, rows, cols )
                       )
              );

}
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));
}
}