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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.87
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
#1

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

24.10.2010, 12:34. Просмотров 4244. Ответов 2
Метки нет (Все метки)

Пожалуйста помогите решить.
Перевод.
Вопрос задачи: наити выход роботу из лабиринта.
Робот проходит только через (.), а это (#) стенка через которые он не может пройти. Надо написать алгоритм прохода робота через лабиринт.
Условие решить через рекурсию.

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


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

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

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

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

Выход из лабиринта - C++
Всем привет, возник вопрос по поводу лабиринта. Посмотрев форум не нашел такого же задания. Суть - написать программу, с помощью которой...

Выход из лабиринта. В чем ошибка? - C++
Не могу понять, почему моя программа иногда выдает ошибку, а иногда работает хорошо. Помогите пожалуйста. #include&lt;iostream&gt; #include...

Прохождение лабиринта: неожиданное поведение программы (найти и исправить ошибки) - C++
Всем доброго времени суток. В общем написал я программу для генерации лабиринта и программу для его прохождения. В первой генерирую...

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

Посоветуйте как лучше найти выход из положения (тема: легкая база данных) - C++
Короче мучаюсь второй день, так как я пишу не черта не выходит, что лучше использовать, какие техники применить, сделать нужно быстро,...

Прохождение лабиринта - C++
Ниже програма ищет маршрут в квадрате, который начинаеться и заканчиваеться в ячейке 1. Посещает все ячейки по одному разу, не попадая в...

2
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,198
Завершенные тесты: 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");
}
3
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
24.10.2010, 17:11  [ТС] #3
Спасибо большое.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2010, 17:11
Привет! Вот еще темы с ответами:

Прохождение лабиринта - C++
Имеется лабиринт. Нужно составить алгоритм, по которому программа найдет выход из лабиринта. мой начальный код. работает нормально,...

Генерация лабиринта - C++
Разработать приложение, генерирующее лабиринт размером m x n клеток. Дополнительные условия: а) Вход и выход – произвольные клетки...

Прохождение лабиринта - C++
Нужно пройти от 1 до 16 самым коротким путем. И вывести на экран количество шагов.

Прохождение лабиринта - C++
Как написать программу для прохождения лабиринта? У меня не получается. Саму программу можно не писать, а только алгоритм дайте и советы....


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru