Минимальное количество шага, чтобы достичь конца

Question

мне нужно рассчитать минимальное количество прыжков, чтобы дойти до конца массива с кубика броска массив значений может быть отрицательным/положительное значение:

• когда положительный ---- > Переместить вперед
• при отрицательном ------> вернуться

Массив может также содержать значение R, что означает, что игрок должен бросить кости снова

Начальная позиция я s, помеченные на нашем массиве с S и конечным положением с E. Положение начала не всегда является первым элементом в массиве, а конечное положение не всегда находится в конце, оно может быть даже до S

Пример: Array = {4 , S, -2,1, R, 4,3,4,3, -5,2, -4, Е}

стартового игрока на позицию S самый быстрый способ достичь Е:

• Бросание кубиков, чтобы иметь 3 и достигнуть кейса R (первый ход)
• снова бросает кости и имеет 6, чтобы добраться до 2-го корпуса (второе движение)
• Jumping 2 случая, чтобы достичь E (третье перемещение)

поэтому лучшим решением для этого примера является: 3 перемещается

Answer 1

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

В вашем случае; рассмотреть превращая ваш массив в графе:

• Каждый индекс массива является узлом в этой графе
• Значение каждой позиции массива говорит кое-что о краев к другим узлам. Например, если a (0) - R; то a (0) будет связано с (1), a (2) .. a (6) - потому что вы можете достичь следующих 6 элементов.

Для начала; Я бы предложил сделать это вручную; просто нарисуйте граф, например массив.

Таким образом, шаги, чтобы решить вашу проблему:

1. Transform ваш массив в графе
2. Поиск сеть для алгоритмов поиска минимальных путей длины в виде графиков
3. Распечатайте этот путь; в результате чего минимальный список от S до E

Реализация оставлена ​​как упражнение для читателя.

Answer 2

Я написал это рабочее решение, которое я разделяю для всех, кто интересуется, но когда дело доходит до большого массива (например, 3000), он выдает ошибку в java-пространстве, поскольку код будет потреблять огромный объем памяти, любую помощь или рекомендации будут оценены

public class Solution { 
static int startPosition; 


public static int compute(BufferedReader br) throws IOException { 
    final int totalNodeCount = getTotalNodeNumber(br); 
    final String caseArray[] = new String[totalNodeCount]; 
    bufferToArray(br, caseArray); 
    startPosition = getStartPosition(caseArray); 
    final boolean visited[] = new boolean[caseArray.length]; 
    int minimumNumberOfMove = 0; 
    final List<Integer> reachableList = new ArrayList<Integer>(); 


    for (int i = 1; i <= 6; i++) 
    { 
     visitedInitilise(visited); 
     if (((startPosition + i) < totalNodeCount) && ((startPosition + i) > 0)) 
      getMinimumNumberOfMoves(caseArray, visited, startPosition + i, 0, reachableList); 
    } 

    // Retriving Minimum number of move from all reachble route 
    if (reachableList.isEmpty()) 
     minimumNumberOfMove = Constants.IMPOSSIBLE; 
    else 

    { 
     minimumNumberOfMove = reachableList.get(0); 
     for (int i = 0; i < reachableList.size(); i++) 
      if (reachableList.get(i) < minimumNumberOfMove) 
       minimumNumberOfMove = reachableList.get(i); 

    } 

    return minimumNumberOfMove; 

} 


static int getStartPosition(String[] plateau){ 

    int startIndex = 0; 
    for (int i = 0; i <= (plateau.length - 1); i++) 
     if (plateau[i].equals("S")) 
     { 
      startIndex = i; 
      break; 
     } 

    return startIndex; 
} 
static void bufferToArray(BufferedReader br, String[] plateau) { 
    String line; 
    int i = 0; 
    try 
    { 
     while ((line = br.readLine()) != null) 
     { 
      plateau[i] = line; 
      i++; 
     } 
    } 
    catch (IOException e) 
    { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 
} 


static int getTotalNodeNumber(BufferedReader br) { 
    int i = 0; 
    try 
    { 
     i = Integer.parseInt(br.readLine()); 
    } catch (NumberFormatException e) 
    { 
     e.printStackTrace(); 
    } catch (IOException e) 
    { 
     e.printStackTrace(); 
    } 
    return i; 
} 
static List<Integer> getMinimumNumberOfMoves(String[] plateau, boolean[] visited, final int currentIndex, 
     int currentNumberOfMoves, List<Integer> list) { 

    Boolean endIsReached = false; 
    Boolean impossible = false; 
    visited[startPosition] = true; 
    // Checking if the current index index is negativ 
    if (currentIndex < 0) 
     impossible = true; 

    while ((endIsReached == false) && (impossible == false) && (visited[currentIndex] == false) 
      && (currentIndex < plateau.length)) 
    { 
     try 
     { 

      switch (plateau[currentIndex]) { 
      case "E": { 
       // if end is reached , pushing number of move into our list 
       endIsReached = true; 
       list.add(currentNumberOfMoves + 1); 
       break; 

      } 

      case "R": { 
       // Marking node as visited 
       visited[currentIndex] = true; 

       for (int i = 1; i <= 6; i++) 
       { 
        // Marking all case after R case as non visited 
        for (int j = currentIndex + 1; j < visited.length; j++) 
         visited[j] = false; 
        // Calculating number of move after R case 
        if (((currentIndex + i) < plateau.length) && (currentIndex > 0)) 
         getMinimumNumberOfMoves(plateau, visited, currentIndex + i, currentNumberOfMoves + 1, list); 
       } 

       break; 
      } 
      default: { 
       // Cheking if node was already visited 
       if (visited[currentIndex] == true) 
       { 
        // Marking all node as non visited 
        visitedInitilise(visited); 

        impossible = true; 
        break; 
       } 
       else 
       { 
        // when the node was not visited before , catch the jump 
        // value 
        int jumpValue = Integer.parseInt(plateau[currentIndex]); 
        // cheking that the next node is not bigger than node 
        // number and not negativ 
        if (((currentIndex + jumpValue) > plateau.length) || (currentIndex < 0)) 
        { 
         impossible = true; 
         break; 
        } 
        else 
        { 
         // Marking node as visited 
         visited[currentIndex] = true; 
         // calculating minimum number of move starting from 
         // this node 
         getMinimumNumberOfMoves(plateau, visited, currentIndex + jumpValue, 
           currentNumberOfMoves + 1, list); 
         break; 
        } 
       } 

      } 

      } 

     } 
     catch (NumberFormatException e) 
     { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     } 

     break; 
    } 
    if (impossible == true) 
     currentNumberOfMoves = 0; 

    return list; 

} 

static void visitedInitilise(boolean visited[]) { 

     for (int i = 0; i <= (visited.length - 1); i++) 
      visited[i] = false; 
    } 

public static void main(String args[]){ 
    String testCaseID = "15"; // Write a test file number from 1 to 15, or 
           // ALL 
    TestCases.test(testCaseID); 
} 

}