Нужно пройти лабиринт, так чтоб нигде не проходить дважды

@Myrbm · Регистрация: 09.04.2009

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

Всем доброго времени суток... Есть задача: Нужно пройти лабиринт, так чтоб нигде не проходить дважды... вроде все сделал, но вот не могу сделать так чтоб проходить перекрестки.... может кто-то подкинет какую то идею на этот счёт...
вот код:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<stdio.h>
#define R 23
#define S 21
   struct Point{
    int r,s;
     };
    void Check (struct Point *pointer);
    void Move  (struct Point *pointer, int dir_r,int dir_s);
 
//void main ()
 int Mase[R][S]= {
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0 ,
    0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,
    0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,
    0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,
    0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,0,0,
    0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,0,0,0,0,
    0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,
    0,0,1,1,0,0,1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,
    0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,
    0,0,1,1,0,0,1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,
    0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,0,
    0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,0,0,0,0,
    0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,0,0,
    0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,
    0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,
    0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    };
     struct Point start,finish,way[600];
 
 
 
  int i,k=0;
 
  void main()
  {
 
 
       { struct Point curr;
    start.r=11;
    start.s=0;
    finish.r=11;
    finish.s=20;
    curr=start;
    way [k]=curr;
    Mase [curr.r][curr.s]=2;
    Check (&curr);
       }
  }
  void Check (struct Point *pcurr)
   {if(pcurr->r == finish.r && pcurr->s==finish.s && k==128)
    { puts ("Finish");
    for (i=0;i<k;i++)
    printf ("%d %d\n",way[i].r, way[i].s );
     return;
    }
 
     Move (pcurr, 0,1);
     Move (pcurr,0,-1);
     Move (pcurr, 1,0);
     Move (pcurr,-1,0);
   }
    void Move (struct Point *pcurr, int dir_r, int dir_s)
      {int cr,cs;
       cr=pcurr->r+dir_r;
       cs=pcurr->s+dir_s;
    if (cr<R && cs<S && Mase [cr][cs]==1)
     { pcurr ->r=cr;
       pcurr ->s=cs;
       way [++k]=*pcurr;
       Mase[cr][cs]=2;
       Check (pcurr);
       pcurr->s=cs-dir_s;
       pcurr->r=cr-dir_r;
       Mase [cr][cs]=1;
     }
    }

@insideone · 09.02.2010, 17:07

Отмечать перекрестки особым числом и разрешать проходить там? (алгоритм поиска перекрестков наврятли сложен) Возможно я не полностью понял что требуется

@Myrbm · 09.02.2010, 17:14 **[ТС]**

to insideone можна и так сделать, вот только мне не получается написать сам алгоритм... Может кто то поможет....

@JKeeJ1e30 · 09.02.2010, 17:17

Парень, не выдумывай. Это классическая задача на обход в глубину. Найди в гугле.

@insideone · 09.02.2010, 17:17

А что сложного в поиске перекрестка?)
Имеем
Mase[i][j]. Перекресток предпологает что выходов с точки более двух) Если перемещение по диагонали запрещено то остается проверить 4 точки - Mase[i+1][j], Mase[i][j+1], Mase[i-1][j], Mase[i][j-1] на наличие в них 1 (путь открыт)

@Myrbm · 09.02.2010, 17:36 **[ТС]**

если вам не трудно, можете написать цикл проверки кодом? Буду очень благодарен..

@insideone · 09.02.2010, 17:42

Можно например так

C++
1
2
3
4
5
6
7
8
9
for (int i = 0; i < R; ++i)
{
   for (int j = 0; j < S; ++j)
   {
      if ( ((i+1) < R) && ((i-1) >= 0) && (j+1) < S) && ((j-1) >= 0) ) // чтобы не выйти за пределы массива
      if ( ( Mase[i+1][j] + Mase[i][j+1] + Mase[i-1][j] +Mase[i][j-1] ) > 2 )
         Mase[i][j] = 2; // особая точка которую можно проходить много раз
   }
}

@Myrbm · 11.02.2010, 20:52 **[ТС]**

Извините, может я дурак, но не мог би кто то компильнуть етот код...

@insideone · 12.02.2010, 02:01

Код не компилится, он странный и неправильный. Может я вообще не понял как он устроен, то ли вы попутали где { открыюваются а где } закрываются. Вы не можете внутри функций объявлять другие функции.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@insideone 3687 / 964 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	09.02.2010, 17:07
	Отмечать перекрестки особым числом и разрешать проходить там? (алгоритм поиска перекрестков наврятли сложен) Возможно я не полностью понял что требуется 0

@Myrbm 0 / 0 / 0 Регистрация: 09.04.2009 Сообщений: 20
	09.02.2010, 17:14 [ТС]
	to insideone можна и так сделать, вот только мне не получается написать сам алгоритм... Может кто то поможет.... 0

@JKeeJ1e30 12 / 12 / 0 Регистрация: 04.02.2010 Сообщений: 45
	09.02.2010, 17:17
	Парень, не выдумывай. Это классическая задача на обход в глубину. Найди в гугле. 0

@Myrbm 0 / 0 / 0 Регистрация: 09.04.2009 Сообщений: 20
	09.02.2010, 17:36 [ТС]
	если вам не трудно, можете написать цикл проверки кодом? Буду очень благодарен.. 0

@insideone 3687 / 964 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	12.02.2010, 02:01
	Код не компилится, он странный и неправильный. Может я вообще не понял как он устроен, то ли вы попутали где { открыюваются а где } закрываются. Вы не можете внутри функций объявлять другие функции. 0