Поиск самого дешевого маршрута в двухмерном массиве (автомобильные сборы) - PullRequest
Новая
       49

Поиск самого дешевого маршрута в двухмерном массиве (автомобильные сборы)

0 голосов
/ 02 апреля 2019

У меня есть это назначение, где мне нужно найти самый дешевый маршрут в заданном 2-D массиве. Допустим, вы автомобиль, начинающий движение в нижнем левом углу массива, и вам нужно добраться до пункта назначения в верхнем правом углу, но вы можете путешествовать только на СЕВЕР и ВОСТОК. Мне нужно написать рекурсивный метод, который

1. должен отображать маршрут, который будет стоить вам НАИМЕНЕЕ сумму платных денег.
2. отображать сумму денег, уплаченную за каждую дорожную пошлину в маршруте, указания о том, как туда добраться, а также общую стоимость. Вот пример вывода: 

Finding the Cheapest Routes:
Grid #1:
12 3 15 8 21
10 2 10 13 9
11 8 19 17 3
Cheapest Route: 11 8 2 3 15 8 21
Direction: EAST NORTH NORTH EAST EAST EAST
Cheapest Cost: $68  
Grid #2:
10 2
15 9
Cheapest Route: 15 9 2
Direction: EAST NORTH 
Cheapest Cost: $26  
Program is Complete

Я прочитал в сетке и у меня есть эти переменные в моем основном методе (BTW gridRows и gridColumns уже были даны и прочитаны (например, для 1-й сетки gridRows равен 3, а gridColumns равна 5) 

int posX = gridRows -1; // keeps track of the x-coord of the position
int posY= 0; // keeps track of the y-coord of the position
int destPosX = gridColumns-1; //both these variables are the destination     of routeFinder
int destPosY = 0; 
int dist = 0;


int minDist = routeFinder(route, posX, posY, Integer.MAX_VALUE, dist,   destPosX, destPosY);

Я изо всех сил пытаюсь создать работающий рекурсивный метод, это то, что я имею до сих пор, я застрял на том, как сохранить путь и как напечатать направление. 

public static int routeFinder (int[][] route, int posX, int posY, int minDist, int dist, int destPosX, int destPosY){       
    //if posX & posY reach the destination
    if(posX == destPosX && posY == destPosY) {
        return Integer.min(dist,minDist);
    }
    //move North
    if(posX -1 >= 0 && posY < route[0].length) {
        minDist = routeFinder(route, posX - 1, posY, minDist, dist + 1, destPosX, destPosY);

    }
    //move East
    if(posX >= 0 && posY +1 < route[0].length) {
        minDist = routeFinder(route, posX, posY + 1, minDist, dist + 1, destPosY, destPosY);
    }
    return minDist;
}

Я застрял, и я не знаю, как действовать дальше ... Мне нужно сначала найти способ найти все возможные маршруты, а затем найти способ отследить самый дешевый маршрут ... любая помощь будет быть оцененным.

...