2

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

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

  public void findPath(int x,int y) {
        ArrayList<Pair<Integer,Integer>> queue = new ArrayList<Pair<Integer,Integer>>();
        queue.add(new Pair<Integer,Integer>(x,y));
        mas[x][y] = 1;
        while (queue.size() > 0)  {
            Pair<Integer,Integer> cur = queue.remove(queue.size() - 1);

//
            if (x < width - 1 && mas[x + 1][y] == 0) {
                queue.add(new Pair<Integer,Integer>(x+1, y));
                mas[x+1][y] = 1;
            }
            if (x > 0 && mas[x - 1][y] == 0) {
                queue.add(new Pair<Integer,Integer>(x-1,y));
                mas[x-1][y] = 1;
            }
            if (y < height - 1 && mas[x][y+1] == 0) {
                queue.add(new Pair<Integer,Integer>(x, y + 1));
                mas[x][y+1] = 1;
            }
            if (y > 0 && mas[x][y-1] == 0) {
                queue.add(new Pair<Integer,Integer>(x, y - 1));
                mas[x][y-1] = 1;
            }
//
        }
    }
2
  • а в чём именно возникла проблема? Алгоритм достаточно простой и известный.
    – pavel
    27 сен 2016 в 13:05
  • pavel Не могу понять его реализацию. Уже пересмотрел все сайты. Никак не могу понять, как его можно применить в моем лабиринте, чтобы смайлик с поставленной точки доходил до выхода. 27 сен 2016 в 13:10

1 ответ 1

2

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

public void getPath(int x,int y){
    while (mas[x][y] > 1){
        System.out.println(x + " " + y);
        if (x < width - 1 && mas[x + 1][y] == mas[x][y] - 1) {
            x++;
            continue;
        }
        if (x > 0 && mas[x - 1][y] == mas[x][y] - 1) {
            x--; 
            continue;
        }
        if (y < height - 1 && mas[x][y+1] == mas[x][y] - 1) {
            y++;
            continue;
        }
        if (y > 0 && mas[x][y-1] == mas[x][y] - 1) {
            y--;
            continue;
        }
    }
    System.out.println(x + " " + y); 
}
5
  • Как понять восстановление пути? Коллекции не нужны в алгоритме вообще никакие? 27 сен 2016 в 14:11
  • Как-то привык писать "восстановление ответа", когда нужно не только число в ответ но и план как его получить. Это из динамического программирования пошло.
    – pavel
    27 сен 2016 в 14:13
  • @Rynkovoy ну я в консоль вывожу, вам думаю сохранять понадобится. Но это уже мелочи.
    – pavel
    27 сен 2016 в 14:14
  • мне не нужно сохранять. простот вывести в лабиринте путь) 27 сен 2016 в 16:12
  • ну это и выводит.
    – pavel
    27 сен 2016 в 16:12

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.