最小數量

Question

我需要計算跳躍的最小數量達到與骰子擲數組值數組的末尾可以是負/正值：

• 當正---- >向前移動
• 當負------>回去

該陣列還可以包含R值，這意味着球員必須扔骰子再次

的起始位置我s在我們的陣列上用S標記並且用E結束位置起始位置並不總是陣列的第一個元素，並且結束位置並不總是在末端，它甚至可以在末尾之前，它甚至可以在S之前例如：Array = {4 ，S，-2,1，R，4,3,4,3，-5,2，-4，E}

S上位置的球員開始以最快的方式到達E：

• 投擲骰子有3個到達R案例（第一招）
• 投擲骰子又有6個達到2個案例（第二個動作）
• 跳躍2案件達到E（第三招）

所以這個例子中，最好的解決辦法是：3個移動

Answer 1

讓我們給你一個提示：關鍵的還是要在這裏學到的：有時你必須改變你的輸入數據，以找到解決問題的好方法。

在你的情況;考慮把你的數組成圖形：

• 每個數組索引是圖
• 各陣列位置的值告訴你一些關於邊緣到其他節點中的一個節點。例如，如果（0）是R，那麼一個（0）將連接到（1），a（2）... a（6） - 因爲你可以達到接下來的6個元素。

對於初學者;我會建議手動這樣做;只是繪製圖例如數組。

因此，步驟解決您的問題：

1. 將您的數組成圖形
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); 
} 

}