Scrooge McDuck

Scrooge McDuck
Description
Scrooge McDuck likes his treasure very much. That is why he likes to play a funny game.

He builds a labyrinth of coins and tries to escape from it. You can think of the labyrinth as a rectangular field. Each cell of the field contains 0 or more coins.

When Scrooge McDuck steps on a cell, he can take only a single coin from this cell, and only if there are any coins. Scrooge McDuck can escape the field, only if he is surrounded by empty cells.

Scrooge McDuck always wants to go to the neighbouring cell with most coins. BUT if there are more than one cells with the same amount of coins (the largest), he chooses a cell (always the largest) from the order left, right, up, down

If Scrooge McDuck cannot go in any direction, he is out of the labyrinth

Examples

Scrooge McDuck is worried, not about his life, but if the coins he collect will be enough. Your task is to tell him how many coins he will collect, following the rules above.

Input
Read from the standard input
On the first line find N and M
The size of the labyrinth
On the next N lines find M integer values, separated by a space
The input data will always be valid and there is no need to check it explicitly
The starting location of Scrooge McDuck will be marked as the only 0
Output
Print to the standard output
On the single line, print the number of coins Scrooge McDuck can collect, following the rules
Contraints
2 <= N <= 10
2 <= M <= 10
Each cell can contain up to 1024 coins
Sample tests
Input
4 3
3 2 4
2 0 3
1 1 5
2 2 5
Output
22
Input
3 3
10 10 0
10 10 10
10 10 10
Output

package Recursion;

import java.util.Scanner;

public class McDuck {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int row = Integer.parseInt(input[0]);
        int col = Integer.parseInt(input[1]);
        int[][] matrix = new int[row][col];
        int startRow = 0;
        int startCow = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] = scanner.nextInt();
                if (matrix[i][j] == 0) {
                    startRow = i;
                    startCow = j;
                }
            }
        }
        System.out.println(solveMcDuck(matrix, startRow, startCow));
    }
    static int coins = 0;
    private static int solveMcDuck(int[][] matrix, int row, int col){

        int left = 0;
        int right = 0;
        int up = 0;
        int down = 0;

    if(outOfMatrix(matrix, row, col - 1) && matrix[row][col-1] > 0){
        left = matrix[row][col-1];
    }
    if(outOfMatrix(matrix, row, col + 1) && matrix[row][col +1] > 0){
        right = matrix[row][col+1];
        }
    if(outOfMatrix(matrix, row - 1, col) && matrix[row -1][col] > 0){
        up = matrix[row-1][col];
    }
    if(outOfMatrix(matrix, row + 1, col) && matrix[row+1][col] >0){
        down = matrix[row+1][col];
    }
     int[] maxCoins = new int[4];
    maxCoins[0] = left;
    maxCoins[1] = right;
    maxCoins[2] = up;
    maxCoins[3] = down;

    int temp = 0;
    int index = -1;

        for (int i = 0; i < maxCoins.length; i++) {
           if(maxCoins[i] > temp){
               temp = maxCoins[i];
               index = i;
           }
        }
        if(index == 0){
            coins++;
            matrix[row][col - 1]--;
            solveMcDuck(matrix, row, col-1);
        }
        if(index == 1){
            coins++;
            matrix[row][col + 1]--;
            solveMcDuck(matrix, row, col+1);
        }
        if(index == 2){
            coins++;
            matrix[row-1][col]--;
            solveMcDuck(matrix, row-1, col);
        }
        if(index == 3){
            coins++;
            matrix[row+1][col]--;
            solveMcDuck(matrix, row+1, col);
        }
        return coins;
    }

    private static boolean outOfMatrix(int[][] matrix, int row, int col){
        return row < matrix.length && row >= 0 && col < matrix[0].length && col >= 0;
    }
}