Google Foo.Bar - Вопрос о том, чтобы не стать добровольным - PullRequest
Новая
       22

Google Foo.Bar - Вопрос о том, чтобы не стать добровольным

0 голосов
/ 14 октября 2018

Итак, с кодом, который у меня есть сейчас, я прохожу 9/10 тестовых случаев.Я использовал поиск в ширину, чтобы найти кратчайший путь, и он, кажется, работает для всего, что я пытаюсь.Вот метод, чтобы найти путь с остальной частью кода, включенного ниже. 

public static int findShortestKnightPath(int src, int dest) {
    if (src == dest)
        return 0;

    int[][] offset = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};
    int currentMoves = 0;

    HashSet<Integer> visitedSpaces = new HashSet<>();
    Queue<int[]> moveQueue = new LinkedList<>();

    //queue holds location and number of moves
    int[] move = {src, 0};
    moveQueue.add(move);

    while (!moveQueue.isEmpty()) {
        int[] queuePoll = moveQueue.poll();
        int current = queuePoll[0];
        currentMoves = queuePoll[1];
        currentMoves++;

        visitedSpaces.add(current);

        int[] currentCoords = grid.getCoords(current);

        for (int i = 0; i < grid.gridSize(); i++) {
            int newX = currentCoords[0] + offset[i][0];
            int newY = currentCoords[1] + offset[i][1];
            int newLocation = 0;
            if (grid.isWithinGrid(newX, newY))
                newLocation = grid.getLocation(newX, newY);

            if (newLocation == dest) {
                return currentMoves;
            }

            if (!visitedSpaces.contains(newLocation)) {
                int[] queueArr = {newLocation, currentMoves};
                moveQueue.add(queueArr);
            }
            visitedSpaces.add(newLocation);
        }
    }

    return currentMoves;
}

Вставить весь код: https://pastebin.com/j7dwzSFg Описание проблемы: https://i.imgur.com/cLfMogc.png

РЕДАКТИРОВАТЬ:После грубой форсировки я смог выяснить тестовый пример, проблема в том, что когда коню приходится перемещаться из одного угла доски в противоположный угол (что должно занять 6 ходов), на самом деле требуется 7.

...