到达终点的最小移动次数

Question

我需要计算用 dice throw Array Value 到达数组末尾的最少跳转次数 Array Value may be negative/positive value:

当为正时----> 向前移动
当否定时 ------> 返回

数组中可能还包含R值，即玩家必须再次掷骰子

开始位置在我们的Array上用S标记，结束位置用E标记开始位置并不总是Array的第一个元素，结束位置也不总是在末尾，甚至可以在S之前

示例：数组 = {4, S, -2,1, R, 4,3,4,3,-5,2,-4, E}

玩家从 S 位置开始到达 E 的最快方式：

掷骰子得到 3 并到达 R 情况（第一步）
再次掷骰子，6点到达2 Case（第二步）
跳2个箱子到达E（第三步）

所以这个例子的最佳解决方案是：3 步

Answer 1

让我们给你一个提示：这里要学习的关键是：有时你必须转换输入数据才能找到解决问题的好方法。

在你的情况下；考虑将您的数组转换为图表：

每个数组索引都是该图中的一个节点
每个数组位置的值告诉您一些关于其他节点的边的信息。例如，如果 a(0) 是 R；那么 a(0) 将连接到 a(1)、a(2) .. a(6) - 因为您可以到达接下来的 6 个元素。

初学者；我建议手动执行此操作；只需为示例数组绘制图形。

所以，解决您问题的步骤：

将数组转换为图形
在网上搜索算法以在图中查找最小长度路径
打印出那个路径；导致从 S 到 E

实施留作 reader 的练习。

Answer 2

我写了这个可行的解决方案，我将它分享给任何感兴趣的人，但是当涉及到处理大数组（例如 3000）时，它会抛出一个 java 堆 space错误，因为代码会消耗大量内存，任何帮助或建议将不胜感激

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

}

到达终点的最小移动次数

Minimum Number of move to reach End

java

arrays

minimum