В программе не до конца выполняется цикл while

У меня программа ищет выход из лабиринта. На входе текстовый файл, в котором 0-проход, 1-стена, 2-вход, 3-выход.
Нужно получить выходной файл, в котором 1- путь, остальное-0.
У меня для одного лабиринта выполнилась программа, а для другого (там, где есть тупик) нет. Хотя, я прописала, что делать в этом случае, но программа почему-то не заходит в этот if.
Подскажите, как исправить.
Самое странное, что в цикле внешнем while программа доходит до проблемной точки, а дальше не идет, ничего не печатает.
Мне было бы понятно, если бы зациклилась. А такое поведение не понятно.

Я код в виде архива прикрепила.
Подскажете?

Вложения

Labirint_main.rar (17.40 Мб, 14 просмотров)

0

Условие такое в цикле.
Что если одна из координат совпадает с точкой выхода, цикл прерывается.

0

Спасибо!
Это поправила, но теперь доходит до следующего тупика и начинает вся время двигаться назад, ко входу, а не к выходу.
Что еще поправить? Где-то забыла статус сменить на passed?
Во вложении поправленный главный файл.

Вложения

Labirint_main.rar (1.6 Кб, 11 просмотров)

0

Откуда же мне знать?
Я не знаю по каком алгоритму ищется выход в этой программе.

Добавлено через 42 минуты
Похоже на попытку поиска в ширину(ещё называют Волновым методом), только криво.

0

Да, как-то так. Только не вижу, где опять ошибка. За свежим, внимательным взглядом обращаюсь.

0

Сообщение от Ната87Ната Да, как-то так.

То что там есть сейчас, нет особого смысла исправлять.
Просто написать заново без всех этих костылей.

0

Что за костыли? Что так сильно не понравилось то???

0

Да мне всё нравится.
Просто в коде поиска пути, нет законченной логики. И так же неоднозначностей.
Поэтому править его можно бесконечно.
Навскидку намешена логика поиска в глубину и поиска в ширину, что уже нехорошо.
Есть множество разных состояний, исключительных, что приводит к ещё большей запутанности очень простой задачи.

Сообщение от Ната87Ната доходит до следующего тупика и начинает вся время двигаться назад, ко входу, а не к выходу

Он же не знает где выход, так что будет искать везде.
Почему идет назад? А почему нет? Клетка не всегда удаляется из вектора, как обработанная.
И при след. цикле while, опять будет обрабатывать те же самые клетки.
Нет проверки точки c(которая уже в списке на обработку) на passed.

Из постановки задачи уже неоднозначность:

Сообщение от Ната87Ната Нужно получить выходной файл, в котором 1- путь, остальное-0.

На самом деле путь не будет известен.
Откуда, куда и по каким клеткам прошел персонаж???
И в реализации/задумке поиска пути такая же ситуация.

0

Но это не совсем граф, чтобы был четко поиск в ширину. А так проверяю 4 соседние клетки (по диагонали сказано нельзя ходить). Стена (1)- не идем, по уже прошедшим тоже не идем (только чтобы из тупика выбраться), а если выбор из двух, то уж первую в векторе из 4-х, что не всегда удачно...

0

Сообщение от Ната87Ната Но это не совсем граф, чтобы был четко поиск в ширину.

Это как раз таки совсем граф.
Каждая вершина адресуется координатами однозначно.
Каждая связь вершины(точки (x,y)) однозначно определяется с другой точкой(связь есть только в случае одинаковой координаты x или y).
Такую систему можно легко воспринимать как граф, что и успешно используется в алгоритме Ли.

И что я успешно могу продемонстрировать сам, просто описав интерфейс графа над полем игры.

0

У меня заработало

Добавлено через 1 минуту
Там ошибка была в том, что перепутала размеры по х и у в функции проверки на то, что не вышли за границы лабиринта.

0

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

Миниатюры

   

0

Создаешь таблицу. 1 - стены, 2 - вход (старт), 3 - выход (финиш). Остальные нули.

- Ищешь клетку со входом (2), проверяешь соседние клетки - и если в них 0 - записываешь в них, ну скажем, 11.
- Ищешь клетки с 11, проверяешь соседние, если в них 0 - записываешь 12
- И так далее, пока не дойдешь до выхода (3) - путь найден, или пока не возникнет такая ситуация, что не удастся поставить ни одной следующей цифры - путь не найден.

Потом нужно найти реальный кратчайший путь от 3 к 2. Допустим, цифра 3 нашлась после 15, записываешь в ячейку 15 (например) 115. Находим вокруг 115 точку 14 - если их несколько, выбираешь первую попавшуюся или рэндомом. Записываешь в точку 14 - 114. И так далее до 111, которая и будет граничить с входом 2. Потом проходишь по таблице и вместо всех 2-х значных чисел возвращаешь нули. А оставшиеся 3-х значные 111, 112, 113, 114 и 115 и будут путем от входа 2 к выходу 3.

Как то так.

0

alexu_007, это и есть Алгоритм Ли/Волновой метод/Волновая трассировка.

Сообщение от Ната87Ната У меня заработало

Молодец.

Добавлено через 6 минут

Сообщение от Ната87Ната Правда во все тупики заходит

Проверь на поле 100*100 без стен.

Сообщение от Ната87Ната перепутала размеры по х и у

Поэтому поводу есть совет.
X - это ширина(координата по горизонтали), Y - высота(по вертикали). Так устоялось по декартовой системе координат.
Когда используешь переменные для массива, всегда используется наоборот.
Что бы меньше путать, называть переменные для массива h и w(r/c, row/col), или аналогично.

0