Лабиринт: определить, возможно ли из точки входа добраться до точки выхода

@Dirty_SG · Регистрация: 15.04.2020

Студворк — интернет-сервис помощи студентам

Даны числа n и m. После чего задаётся матрица размером n×m из 0
и 1. Будем считать, что эта матрица задаёт карту лабиринта, при этом 0
является пустым пространством, а 1 стеной. В данном лабиринте будем
считать, что точкой входа является клетка с координатами (1,1), а точкой
выхода (n,m). Необходимо определить, возможно ли из точки входа добраться
до точки выхода, если можно двигаться только в четырёх возможных
направлениях (север, юг, запад, восток) и перемещаться можно только в
свободную клетку.
Пример. Входные данные:
4 5
0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
Выходные данные:
YES

@Shut913 · 19.06.2020, 08:54

Можно сделать через рекурсию, с изменением значений ячеек в которой находится функция с 0 на 1, что б не было зацикливаний

@alexu_007 · 19.06.2020, 10:04

Волновой алгоритм:

@Shut913 · 19.06.2020, 10:37

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
43
44
45
46
#include <iostream>
using namespace std;
 
bool foo(short y, short x, bool** arr,short& m, short& n)
{
    if (y==m-1 && x==n-1) return 1;
    arr[y][x]=1;
    bool result1=0, result2=0, result3=0, result4=0;
    
    if(y-1>=0)
       if(arr[y-1][x]==0)
          result1=foo(y-1,x,arr,m,n);
    
     if(y+1<m)
       if(arr[y+1][x]==0)
          result2=foo(y+1,x,arr,m,n);
 
    if(x-1>=0)
       if(arr[y][x-1]==0)
          result3=foo(y,x-1,arr,m,n);
    
     if(x+1<n)
       if(arr[y][x+1]==0)
          result4=foo(y,x+1,arr,m,n);       
    
    return (result1||result2||result3||result4);
}
 
int main()
{
    short m, n;
    cout<<"enter m, n > ";
    cin>>m>>n;
    
    bool** arr=new bool*[m];
    for (short i=0;i<m;i++)
       arr[i]=new bool[n];
    
    cout<<"enter matrix elements > ";        
    for(short i=0;i<m;i++)
       for(short j=0;j<n;j++)
          cin>>arr[i][j];
    
    cout<<(foo(0,0,arr,m,n)?"true":"false");
    return 0;
}

@Simonaakk · 22.08.2020, 21:40

Shut913, а можно поменять код так, чтобы начальную и конечную клетку задавать с клавиатуры?

@AndryS1 · 22.08.2020, 23:30

Сообщение от Simonaakk

а можно поменять код так

можно

@Simonaakk · 24.08.2020, 07:04

С кодом можете помочь, очень прошу

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Dirty_SG 0 / 0 / 0 Регистрация: 15.04.2020 Сообщений: 5

	Лабиринт: определить, возможно ли из точки входа добраться до точки выхода 18.06.2020, 19:03. Показов 3478. Ответов 6 Метки лабиринт, массив (Все метки) Даны числа n и m. После чего задаётся матрица размером n×m из 0 и 1. Будем считать, что эта матрица задаёт карту лабиринта, при этом 0 является пустым пространством, а 1 стеной. В данном лабиринте будем считать, что точкой входа является клетка с координатами (1,1), а точкой выхода (n,m). Необходимо определить, возможно ли из точки входа добраться до точки выхода, если можно двигаться только в четырёх возможных направлениях (север, юг, запад, восток) и перемещаться можно только в свободную клетку. Пример. Входные данные: 4 5 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 Выходные данные: YES 0

@Shut913 151 / 103 / 49 Регистрация: 21.11.2019 Сообщений: 285
	19.06.2020, 08:54
	Можно сделать через рекурсию, с изменением значений ячеек в которой находится функция с 0 на 1, что б не было зацикливаний 0

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,267
	19.06.2020, 10:04
	Волновой алгоритм: Миниатюры 0

@Simonaakk 0 / 0 / 0 Регистрация: 23.07.2020 Сообщений: 43
	22.08.2020, 21:40
	Shut913, а можно поменять код так, чтобы начальную и конечную клетку задавать с клавиатуры? 0

@Simonaakk 0 / 0 / 0 Регистрация: 23.07.2020 Сообщений: 43
	24.08.2020, 07:04
	С кодом можете помочь, очень прошу 0

Лабиринт: определить, возможно ли из точки входа добраться до точки выхода

Решение