Задано матрицу размером с занятыми (содержат -1) и свободными (содержат 0) клеточками, а также координаты 2ух пустых ячеек, заданые парами чисел. Назовём ходом переход на соседнюю (по вертикали или горизонтали) свободную клеточку. Выяснить, возможен ли переход между задаными клеточками.
------------Очень прошу, помогите. Заранее спасибо.
программа "Лабиринт". Помогите с решением
Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain
Данную задачу можно решить только полным перебором. Например рекурсией.
int map[N][N];
int used[N][N]; // то где мы были. В начале забит 0
int xk,yk; - координаты выхода.
int a(int x, int y){
if (map[x][y]==-1)
return 0;// сюда нельзя
if ((x==xk) && (y = yk))
return 1; //Мы вышли.
//ломимся в соседние клетки
if(!used[x-1][y]){
used[x-1][y] = 1;
if (a(x-1, y)) return 1;
used[x-1][y] = 0;
};
if(!used[x+1][y]){
used[x+1][y] = 1;
if (a(x+1, y)) return 1;
used[x+1][y] = 0;
};
if(!used[x][y-1]){
used[x][y-1] = 1;
if (a(x, y-1)) return 1;
used[x][y-1] = 0;
};
if(!used[x][y+1]){
used[x][y+1] = 1;
if (a(x, y+1)) return 1;
used[x][y+1] = 0;
};
return 0; //отсюда нельзя выйти
};
Можно оптимизировать поиск, если предположить, что к выходу быстрее прорываться напрямую, и сортировать порядок проверки, по приближению к выходу.
Для того, чтобы запустить поиск нужно вызвать а(х начальное, у начальное). Вернете 0 или 1.
int map[N][N];
int used[N][N]; // то где мы были. В начале забит 0
int xk,yk; - координаты выхода.
int a(int x, int y){
if (map[x][y]==-1)
return 0;// сюда нельзя
if ((x==xk) && (y = yk))
return 1; //Мы вышли.
//ломимся в соседние клетки
if(!used[x-1][y]){
used[x-1][y] = 1;
if (a(x-1, y)) return 1;
used[x-1][y] = 0;
};
if(!used[x+1][y]){
used[x+1][y] = 1;
if (a(x+1, y)) return 1;
used[x+1][y] = 0;
};
if(!used[x][y-1]){
used[x][y-1] = 1;
if (a(x, y-1)) return 1;
used[x][y-1] = 0;
};
if(!used[x][y+1]){
used[x][y+1] = 1;
if (a(x, y+1)) return 1;
used[x][y+1] = 0;
};
return 0; //отсюда нельзя выйти
};
Можно оптимизировать поиск, если предположить, что к выходу быстрее прорываться напрямую, и сортировать порядок проверки, по приближению к выходу.
Для того, чтобы запустить поиск нужно вызвать а(х начальное, у начальное). Вернете 0 или 1.
-
Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Нет, господин LanDyx, не только методом перебора.
Это неимоверно трудоёмкий алгоритм. Думаю, он начнёт испытывать трудности уже после того, как размерность входной матрицы привысит 20 X 20. Привожу алгоритм, который без особых временных затрат (и что не менее важно без использования четырёхкратной рекурсии, которая жрёт стэк, как свинья помои) решает эту задачу для матрицы 200 X 200 менее, чем за секунду, более того выдаёт найкратчайший путь.
Пусть ячейки матрицы могуть принимать следующие значания:
0 - пусто
1 - стена
2 - человечек в лабиринте (клетка с таким значением может быть только одна)
Тогда алгоритм следующий:
1. Устанавливаем значение переменной curr в 2.
2. Пробегаем по всем клеткам матрицы и находим все клетки матрицы, которые равны curr.
3. Для каждой такой клетки изучаем её "соседей".
4. Если кто-то из соседей равен нулю (т.е. пустой), то помещаем туда число (curr + 1).
5. Если ни одна клетка за этот проход не изменилась, значит пути нет, конец алгоритма.
6. Если клетка "выход из лабиринта" всё ещё хранит ноль, то увеличиваем curr на 1 и переходим на пункт 2.
7. Теперь клетка "выход из лабиринта" не ноль (иначе бы мы вышли из программы по условию в пункте 5). Предположим она хранит значение finish.
8. Тогда количество совершенных ходов равняется (finish - 2).
9. Чтобы выписать пройденный человечком путь, нужно двигаться от клетки "выход из лабиринта" ища в соседях сначала значение (finish - 1), затем (finish - 2) и т.д., то тех пор, пока текущее значение клетки не станет равным 2.
Порядок, в котором будут "опрашиваться" соседи в пункте 9, коренным образом влияет на искомый путь, но в любом случае путь будет кратчайшим.
P.S. Использовал этот алгоритм, когда писал собственный клон игрушки "Lines" для обеспечения перемещения шарика из клетки "n" в клетку "m". Игровое поле с расположеннеми на нём шариками, по сути дела, - тот же лабиринт. Самые лучшие отзывы!
Это неимоверно трудоёмкий алгоритм. Думаю, он начнёт испытывать трудности уже после того, как размерность входной матрицы привысит 20 X 20. Привожу алгоритм, который без особых временных затрат (и что не менее важно без использования четырёхкратной рекурсии, которая жрёт стэк, как свинья помои) решает эту задачу для матрицы 200 X 200 менее, чем за секунду, более того выдаёт найкратчайший путь.
Пусть ячейки матрицы могуть принимать следующие значания:
0 - пусто
1 - стена
2 - человечек в лабиринте (клетка с таким значением может быть только одна)
Тогда алгоритм следующий:
1. Устанавливаем значение переменной curr в 2.
2. Пробегаем по всем клеткам матрицы и находим все клетки матрицы, которые равны curr.
3. Для каждой такой клетки изучаем её "соседей".
4. Если кто-то из соседей равен нулю (т.е. пустой), то помещаем туда число (curr + 1).
5. Если ни одна клетка за этот проход не изменилась, значит пути нет, конец алгоритма.
6. Если клетка "выход из лабиринта" всё ещё хранит ноль, то увеличиваем curr на 1 и переходим на пункт 2.
7. Теперь клетка "выход из лабиринта" не ноль (иначе бы мы вышли из программы по условию в пункте 5). Предположим она хранит значение finish.
8. Тогда количество совершенных ходов равняется (finish - 2).
9. Чтобы выписать пройденный человечком путь, нужно двигаться от клетки "выход из лабиринта" ища в соседях сначала значение (finish - 1), затем (finish - 2) и т.д., то тех пор, пока текущее значение клетки не станет равным 2.
Порядок, в котором будут "опрашиваться" соседи в пункте 9, коренным образом влияет на искомый путь, но в любом случае путь будет кратчайшим.
P.S. Использовал этот алгоритм, когда писал собственный клон игрушки "Lines" для обеспечения перемещения шарика из клетки "n" в клетку "m". Игровое поле с расположеннеми на нём шариками, по сути дела, - тот же лабиринт. Самые лучшие отзывы!
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Если можна, то опиши пожалуйста это на языке прогрммирования. Не всю прогу, конечно, а сам принцип. ПожалстаааааRomeo писал(а):Нет, господин LanDyx, не только методом перебора.
Это неимоверно трудоёмкий алгоритм. Думаю, он начнёт испытывать трудности уже после того, как размерность входной матрицы привысит 20 X 20. Привожу алгоритм, который без особых временных затрат (и что не менее важно без использования четырёхкратной рекурсии, которая жрёт стэк, как свинья помои) решает эту задачу для матрицы 200 X 200 менее, чем за секунду, более того выдаёт найкратчайший путь.
Пусть ячейки матрицы могуть принимать следующие значания:
0 - пусто
1 - стена
2 - человечек в лабиринте (такая клетка может быть только одна)
тогда алгоритм следующий:
1. Устанавливаем значение переменной curr в 2.
2. Пробегаем по всем клеткам матрицы и находим все клетки матрицы, которые равны curr.
3. Для всех таких клеток изучаем её "соседей".
4. Если кто-то из соседей равен нулю (т.е. пустой), то помещаем туда число (curr + 1).
5. Если ни одна клетка за этот проход не изменилась, значит пути нет, конец алгоритма.
6. Если клетка "выход из лабиринта" всё ещё хранит ноль, то переходим на пункт 2.
7. Теперь клетка "выход из лабиринта" не ноль, предположим она хранит значение finish.
8. Тогда количество совершенных ходов равняется (finish - 2).
9. Чтобы выписать пройденный человечком путь, нужно двигаться от клетки "выход из лабиринта" ища в соседях сначала значение (finish - 1), затем (finish - 2) и т.д., то тех пор, пока текущее значение клетки не станет равным 2.
Да... Это есть хорошо...Romeo писал(а):Нет, господин LanDyx, не только методом перебора.
Это неимоверно трудоёмкий алгоритм. Думаю, он начнёт испытывать трудности уже после того, как размерность входной матрицы привысит 20 X 20. Привожу алгоритм, который без особых временных затрат (и что не менее важно без использования четырёхкратной рекурсии, которая жрёт стэк, как свинья помои) решает эту задачу для матрицы 200 X 200 менее, чем за секунду, более того выдаёт найкратчайший путь.
Пусть ячейки матрицы могуть принимать следующие значания:
0 - пусто
1 - стена
2 - человечек в лабиринте (такая клетка может быть только одна)
тогда алгоритм следующий:
1. Устанавливаем значение переменной curr в 2.
2. Пробегаем по всем клеткам матрицы и находим все клетки матрицы, которые равны curr.
3. Для всех таких клеток изучаем её "соседей".
4. Если кто-то из соседей равен нулю (т.е. пустой), то помещаем туда число (curr + 1).
5. Если ни одна клетка за этот проход не изменилась, значит пути нет, конец алгоритма.
6. Если клетка "выход из лабиринта" всё ещё хранит ноль, то переходим на пункт 2.
7. Теперь клетка "выход из лабиринта" не ноль, предположим она хранит значение finish.
8. Тогда количество совершенных ходов равняется (finish - 2).
9. Чтобы выписать пройденный человечком путь, нужно двигаться от клетки "выход из лабиринта" ища в соседях сначала значение (finish - 1), затем (finish - 2) и т.д., то тех пор, пока текущее значение клетки не станет равным 2.
-
Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Не могу. О тебе забочусь. Реализуешь этот алгоритм сам - станешь великим программеромЕсли можна, то опиши пожалуйста это на языке прогрммирования. Не всю прогу, конечно, а сам принцип. Пожалстааааа
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
OK, ну тогда хотя бы распиши поподробней эти пременные curr и т.д. Если не сложно конешноRomeo писал(а):Не могу. О тебе забочусь. Реализуешь этот алгоритм сам - станешь великим программеромЕсли можна, то опиши пожалуйста это на языке прогрммирования. Не всю прогу, конечно, а сам принцип. Пожалстааааа
-
Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Давай лучше так: ты пробуешь справиться сам, а если возникают конкретные вопросы и самому никак не справиться - тогда я на них отвечаю. Таким образом убьём сразу двух зайцев: и я время сэкономлю и ты експы больше получишь.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
*deleting message*
Сорри, не подумав сказал =)
Сорри, не подумав сказал =)
Удачи... =)
-
Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
[offtopic]
Флэймим, господин Acidy. Уровень подготовки ведь у всех разный, не стоит превозносить себя, также, как занижать достижения других.
[/offtopic]
Флэймим, господин Acidy. Уровень подготовки ведь у всех разный, не стоит превозносить себя, также, как занижать достижения других.
[/offtopic]
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.