Блог

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

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

Этап

Вам предоставляется 2d-массив, в котором 0's обозначается недопустимый путь и 1's обозначается допустимый путь. Насколько я знаю, вам разрешено манипулировать данными массива, по которому вы перемещаетесь, поэтому я отмечаю пройденный путь 2's .

Цель

Вам нужно рекурсивно найти и распечатать все пути от origin до exit . Существует четыре лабиринта, некоторые с несколькими путями, тупиками или циклами.

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

Хотя это работает в большинстве случаев, это приводит к сбою в случае, когда первое место, которое он проверяет, оказывается местом, откуда вы пришли. На этом этапе он возвращается и завершается преждевременно.

Из-за этого мне нужно найти способ разумно начать сканирование (по часовой стрелке или против часовой стрелки) в зависимости от того, откуда вы пришли, чтобы это место всегда проверялось последним.

Вот некоторый код, описывающий процесс (примечание: крайние случаи обрабатываются до этого, поэтому нам не нужно беспокоиться об этом):

 private static void main()
{
    int StartX = ;//Any arbitrary X
    int StartY = ;//Any arbitrary Y
    String Path = ""; //Recursive calls will tack on their location to this and print only when an exit path is found.
    int[][] myArray = ;//We are given this array, I just edit it as I go
    Navigator(StartX, StartY, Path, myArray);
}

private static void Navigator(int locX, int locY, String Path, int[][] myArray)
{
    int newX = 0; int newY = 0;
    Path = Path.concat("[" locX "," locY "]");

//Case 1: You're on the edge of the maze
    boolean bIsOnEdge = (locX == 0 || locX == myArray.length-1 || locY == 0 || locY == myArray[0].length-1);
    if (bIsOnEdge)
    {
        System.out.println(Path);
        return;
    }

    int[][] Surroundings = surroundingsFinder(locX, locY, myArray);

    for (int i = 0; i <= 7; i  )
    {
//Case 2: Path encountered
        if (Surroundings[0][i] == 1) 
        {
            myArray[locX][locY] = 2;
            newX = Surroundings[1][i];
            newY = Surroundings[2][i];
            Navigator(newX, newY, myArray, Path);
        }

//Case 3: Breadcrumb encountered
        if (Surroundings[0][i] == 2)
        {
            myArray[locX][locY] = 1;
            return;
        }
    }
}

//generates 2D array of your surroundings clockwise from N to NW
//THIS IS THE PART THAT NEEDS TO BE IMPROVED, It always starts at A.
//
//  H A B
//  G - C
//  F E D
//
static int[][] surroundingsFinder(int locX, int locY, int[][] myArray)
{
    int[][] Surroundings = new int[3][8];
    for (int i = -1; i <= 1; i  )
    {
        for (int j = -1; j <= 1; j  )
        {

        }
    }

    //Can be done simpler, is done this way for clarity
    int xA = locX-1; int yA = locY; int valA = myArray[xA][yA];
    int xB = locX-1; int yB = locY 1; int valB = myArray[xB][yB];
    int xC = locX; int yC = locY 1; int valC = myArray[xC][yC];
    int xD = locX 1; int yD = locY 1; int valD = myArray[xD][yD];
    int xE = locX 1; int yE = locY; int valE = myArray[xE][yE];
    int xF = locX 1; int yF = locY-1; int valF = myArray[xF][yF];
    int xG = locX; int yG = locY-1; int valG = myArray[xG][yG];
    int xH = locX-1; int yH = locY-1; int valH = myArray[xH][yH];

    int[][] Surroundings = new int[3][8];
    Surroundings[0][0] = valA; Surroundings[1][0] = xA; Surroundings[2][0] = yA;
    Surroundings[0][1] = valB; Surroundings[1][1] = xB; Surroundings[2][1] = yB;
    Surroundings[0][2] = valC; Surroundings[1][2] = xC; Surroundings[2][2] = yC;
    Surroundings[0][3] = valD; Surroundings[1][3] = xD; Surroundings[2][3] = yD;
    Surroundings[0][4] = valE; Surroundings[1][4] = xE; Surroundings[2][4] = yE;
    Surroundings[0][5] = valF; Surroundings[1][5] = xF; Surroundings[2][5] = yF;
    Surroundings[0][6] = valG; Surroundings[1][6] = xG; Surroundings[2][6] = yG;
    Surroundings[0][7] = valH; Surroundings[1][7] = xH; Surroundings[2][7] = yH;

    return Surroundings;
}
  

Кто-нибудь может мне помочь с этим? Как вы можете видеть, surroundingsFinder всегда A сначала находит, а затем B полностью H . Это нормально, если и только если вы ввели из H . Но если сбой в тех случаях, когда вы вводили A , поэтому мне нужно найти способ разумно определить, где start искать. Как только я это узнаю, я, вероятно, смогу адаптировать логику, чтобы я больше не использовал 2D-массив значений. Но пока я не могу придумать логику для интеллектуального поиска!

ПРИМЕЧАНИЕ: я знаю, что Java не оптимизирует среднюю рекурсию. Кажется невозможным заставить хвостовую рекурсию работать для решения такой проблемы.

Решение

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

Более раннее исполнение скрипта указывало «0» в местах с протекторами, а не «2», но по какой-то причине я вообразил, что мне нужно «2», и мне нужно было различать «пройденный путь» и «недопустимый путь».

Фактически, из-за рекурсивного характера проблемы я обнаружил, что на самом деле вы можете решить проблему, записывая только 0 по ходу. Кроме того, мне больше не нужно было отслеживать, откуда я пришел, и вместо проверки по часовой стрелке по матрице я выполнял итерации слева направо по окружающей меня матрице 3×3, пропуская свою собственную ячейку.

Вот завершенный код для такого решения. Он выводится на консоль при нахождении выхода (ребра) и в противном случае отслеживает себя по лабиринту, в комплекте с рекурсией. Для запуска функции вам предоставляется квадратный 2D-массив 0's и 1's где 1 является допустимым путем и 0 недопустимым. Вам также предоставляется набор координат, в которые вы «попали» ( locX , locY ), и пустая строка, которая накапливает координаты, формируя путь, который позже распечатывается ( String Path = "" )

Вот код:

 static void Navigator(int locX, int locY, int[][] myArray, String Path)
{
    int newX = 0;
    int newY = 0;

    Path = Path.concat("[" locX "," locY "]");

    if ((locX == 0 || locX == myArray.length-1 || locY == 0 || locY == myArray[0].length-1))
    {//Edge Found
        System.out.println(Path);
        pathCnt  ;
        myArray[locX][locY] = 1;
        return;
    }

    for (int row = -1; row <= 1; row  )
    {            
        for (int col = -1; col <= 1; col  )
        {
            if (!(col == 0 amp;amp; row == 0) amp;amp; (myArray[locX row][locY col] == 1))
            {   //Valid Path Found
                myArray[locX][locY] = 0;
                Navigator(locX row, locY col, myArray, Path);
            }
        }
    }

    //Dead End Found
    myArray[locX][locY] = 1;
    return;
}       System.out.println(Path);
        pathCnt  ;
        swamp[locX][locY] = 1;
        return;
    }

    for (int row = -1; row <= 1; row  )
    {            
        for (int col = -1; col <= 1; col  )
        {
            if (!(col == 0 amp;amp; row == 0) amp;amp; (swamp[locX row][locY col] == 1))
            {   //Valid Path Found
                swamp[locX][locY] = 0;
                Navigator(locX row, locY col, swamp, Path);
            }
        }
    }

    //Dead End Found
    swamp[locX][locY] = 1;
    return;
}
  

Как вы можете определить сами, каждый раз, когда мы «вводим» ячейку, у нас есть 8 соседей для проверки правильности. Во-первых, чтобы сэкономить время выполнения и избежать выхода из массива во время нашего цикла for (он не может найти myArray[i][j] if i или j указать его снаружи, и он выдаст ошибку), мы проверяем наличие ребер. Поскольку нам задана область нашего болота, мы используем оператор сравнения истинности, который по сути говорит ( "(am I on the top or left edge?) or (am I on the bottom or right edge?)" ) . Если мы находимся на ребре, мы распечатываем путь, который мы удерживаем (благодаря тому deep copy , что у нас есть уникальная копия оригинала Path , которая печатается только в том случае, если мы находимся на ребре, и включает наш полный набор координат).

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

 A B C
D . E
F G H
  

Этот цикл проверяет только для 1's и только снова вызывает функцию, если это произойдет. Почему? Потому что это предпоследний случай. Возникнет только одна дополнительная ситуация, и если мы достигнем конца функции, это означает, что мы попали в этот случай. Зачем писать дополнительный код (проверяя 0's , чтобы конкретно распознать его?

Итак, как я только что упомянул, если мы выйдем из for цикла, это означает, что мы вообще не встретили ни одного 1. Это означает, что мы окружены нулями! Это означает, что мы зашли в тупик, и это означает, что все, что нам нужно сделать, это удалить ошибку из этого экземпляра функции, следовательно, final return; .

В целом, конечная функция проста. Но, исходя из отсутствия фона и необходимости понимать закономерности и значения этих случаев, и после нескольких неудачных попыток это может занять довольно много работы. Я несколько дней работал над совершенствованием этого.

Всем счастливого кодирования!

Похоже, ваша проблема связана с:

 if (Surroundings[0][i] == 2)
{
    myArray[locX][locY] = 1;
    return;
}
  

Возможно, это следует изменить на:

 if (Surroundings[0][i] == 2)
{
    // not sure why you need this if it's already 1
    myArray[locX][locY] = 1;

    // go to next iteration of the "i" loop
    // and keep looking for next available path
    continue;
}
  

Ваш рекурсивный метод автоматически вернется, когда ни одна из окружающих ячеек не удовлетворит условию if (Surroundings[0][i] == 1) .

PS: Принято называть ваши переменные, используя маленькую букву в качестве первого символа. Например: surroundings , path , startX или myVar