Форум программистов, компьютерный форум CyberForum.ru

Найти выход из лабиринта - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.87
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
24.10.2010, 12:34     Найти выход из лабиринта #1
Пожалуйста помогите решить.
Перевод.
Вопрос задачи: наити выход роботу из лабиринта.
Робот проходит только через (.), а это (#) стенка через которые он не может пройти. Надо написать алгоритм прохода робота через лабиринт.
Условие решить через рекурсию.

Первая линия включает в себя N и M (2 <= n,m <= 6).
Это матрица NxM состайт только из "#" и ".".
"#" стены
"." проход


Пример:
Ввод:
3 3
.#.
..#
#..
Вывод
YES

Ввод 2:
6 5
.....
####.
.....
.###.
....#
###..
Вывод 2:
YES

Ввод 3:
3 3
.#.
..#
.#.
Вывод 3:
NO

это перевод задачи, если нужен оригинал могу и его написать.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2010, 12:34     Найти выход из лабиринта
Посмотрите здесь:

C++ Выход из лабиринта. В чем ошибка?
Прохождение лабиринта C++
C++ Прохождение лабиринта
Проход лабиринта в C++ C++
C++ Дан проходной лабиринт с одним входом и выходом. Найти кратчайший путь для прохождения этого лабиринта
C++ Прохождение лабиринта
Выход из лабиринта C++
Прохождение лабиринта C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
24.10.2010, 15:23     Найти выход из лабиринта #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <limits>
 
using namespace std;
 
const int maxN = 6, maxM = 6;
typedef bool Labyrinth[maxN + 2][maxM + 2];
 
bool PathExists(Labyrinth& lab, int y1, int x1, int y2, int x2)
{
    lab[y1][x1] = false;
    if (y1 == y2 && x1 == x2)
        return true;
    const struct {int y; int x;} dir[] = {
        {-1, 00}, {00, -1}, {00, +1}, {+1, 00}};
    for (int i = 0; i < sizeof(dir) / sizeof(dir[0]); i++)
        if (lab[y1 + dir[i].y][x1 + dir[i].x] &&
            PathExists(lab, y1 + dir[i].y, x1 + dir[i].x, y2, x2))
            return true;
    return false;
}
 
// zero-initialized
Labyrinth lab;
 
int main()
{
    int n, m;
    cin >> n >> m;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            lab[i][j] = c == '.';
        }
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }
    cout << (PathExists(lab, 1, 1, n, m) ? "YES" : "NO");
}
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
24.10.2010, 17:11  [ТС]     Найти выход из лабиринта #3
Спасибо большое.
Yandex
Объявления
24.10.2010, 17:11     Найти выход из лабиринта
Ответ Создать тему
Опции темы

Текущее время: 18:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru