Developing.ru

Задано матрицу размером с занятыми (содержат -1) и свободными (содержат 0) клеточками, а также координаты 2ух пустых ячеек, заданые парами чисел. Назовём ходом переход на соседнюю (по вертикали или горизонтали) свободную клеточку. Выяснить, возможен ли переход между задаными клеточками.
------------Очень прошу, помогите. Заранее спасибо.

Данную задачу можно решить только полным перебором. Например рекурсией.

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.

Нет, господин 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". Игровое поле с расположеннеми на нём шариками, по сути дела, - тот же лабиринт. Самые лучшие отзывы!

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 писал(а):

Если можна, то опиши пожалуйста это на языке прогрммирования. Не всю прогу, конечно, а сам принцип. Пожалстааааа

Не могу. О тебе забочусь. Реализуешь этот алгоритм сам - станешь великим программером

OK, ну тогда хотя бы распиши поподробней эти пременные curr и т.д. Если не сложно конешно

Давай лучше так: ты пробуешь справиться сам, а если возникают конкретные вопросы и самому никак не справиться - тогда я на них отвечаю. Таким образом убьём сразу двух зайцев: и я время сэкономлю и ты експы больше получишь.

*deleting message*
Сорри, не подумав сказал =)

[offtopic]
Флэймим, господин Acidy. Уровень подготовки ведь у всех разный, не стоит превозносить себя, также, как занижать достижения других.
[/offtopic]