Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > поиск выхода из лабиринта

Автор: ShadowC 24.10.2011, 18:13

задача заключается вот в чем,лабиринт это двумерный массив символом 12x12 '.'-это пустая клетка. '#'-стена

char x[12][12]={{'#','#','#','#','#','#','#','#','#','#','#','#'},{'#','.','.','.','#','.','.','.','.','.','.','#'},{'.','.','#','.','#','.','#','#','#','#','.','#'},{'#','#','#','.','#','.','.','.','.','#','.','#'},{'#','.','.','.','.','#','#','#','.','#','.','.'},{'#','#','#','#','.','#','.','#','.','#','.','#'},{'#','.','.','#','.','#','.','#','.','#','.','#'},{'#','#','.','#','.','#','.','#','.','#','.','#'},{'#','.','.','.','.','.','.','.','.','#','.','#'},{'#','#','#','#','#','#','.','#','#','#','.','#'},{'#','.','.','.','.','.','.','#','.','.','.','#'},{'#','#','#','#','#','#','#','#','#','#','#','#',}};

это уже готовый лабиринт.
нужно построить рекурсивную функцию нахождения пути из лабиринта,двигаться всегда надо касаясь правой рукой стены.
мои соображения
x[y][z] -может иметь лишь 4 возможных вариаций
x[--y][z]
x[++y][z]
x[y][++z]
x[y][--z]

только как реализовать рекурсивную функцию используя это в голову не приложу,а самое главное,я не могу понять как выйти из такого рода рекурсивной функции когда работал с числами возвращалась единица,а что возвращать при работе с символами непонятно

Автор: baldina 24.10.2011, 18:22

Цитата(ShadowC @ 24.10.2011, 18:13

)

x[y][z] -может иметь лишь 4 возможных вариаций
x[--y][z]
x[++y][z]
x[y][++z]
x[y][--z]

я бы сказал x[y-1][z], x[y+1][z] и т.д.

1. определить, не находимся ли мы в выходе, т.е. если наши координаты либо 0 либо максимальное значение (11)
2. если нет, определить следующий допустимый шаг (y1, z1), т.е. рассмотреть последовательно варианты y+1, z+1, y-1, z-1. след. шаг допустим, если в новой позиции точка
3. вызвать себя рекурсивно с параметрами y1, z1

Автор: newbee 24.10.2011, 18:23

Код


void move(pos){
 if(is_finish(pos))
  BINGO!
 if(may_move_bottom(pos))
  return move(pos(pos.x,pos.y-1));
 if(may_move_right(pos))
  return move(pos(pos.x+1,pos.y));
 if(may_move_top(pos))
  return move(pos(pos.x,pos.y+1));
 if(may_move_left(pos))
  return move(pos(pos.x-1,pos.y));
 SHIT_HAPPENS!
}

Автор: ShadowC 24.10.2011, 18:27

Цитата(newbee @ 24.10.2011, 18:23)

Код


void move(pos){
 if(is_finish(pos))
  BINGO!
 if(may_move_bottom(pos))
  return move(pos(pos.x,pos.y-1));
 if(may_move_right(pos))
  return move(pos(pos.x+1,pos.y));
 if(may_move_top(pos))
  return move(pos(pos.x,pos.y+1));
 if(may_move_left(pos))
  return move(pos(pos.x-1,pos.y));
 SHIT_HAPPENS!
}

а как у тебя определяется куда должно быть совершено движение? и как у тебя определяется конечная позиция?

Автор: newbee 24.10.2011, 18:41

Цитата(ShadowC @ 24.10.2011, 19:27

)

а как у тебя определяется куда должно быть совершено движение? и как у тебя определяется конечная позиция?

Я привела общий алгоритм выхода из лабиринта. Только что сообразила, что он кривой, так как не учитывает то, что пытаться двигаться на предыдущую посещенную клетку можно только в крайнем (последнем) случае - иначе рекурсия просто зациклится. Этот момент предлагаю тебе самому доработать smile

Функции may_move_* определяют, можно ли из заданной точки двигаться в одну из сторон, то есть в реализации например may_move_right должна стоять проверка, не является ли символ справа от текущей позиции решеткой. is_finish определят, находится символ ли в текущей позиции в конце лабиринта, можешь в качестве конца использовать '$' и сверяться с ним, например.

Автор: ShadowC 24.10.2011, 18:54

обьясни пожалуйста еще вот это

pos(pos.x-1,pos.y) дело в том что я с таким синтаксисом не знаком

Автор: newbee 24.10.2011, 19:05

ShadowC, это псевдокод. Функция принимает текущую точку pos, которая характеризуется двумя координатами x и y. И далее она вызывает себя же с новой сдвинутой в одну из четырех сторон точкой.

Ну, например:

Код


struct pos{
 int x,y;
 pos(int _x, int _y):x(_x),y(_y){}
};

void move(struct pos const &p){
 ...
 if(may_move_bottom(p))
  return move(pos(p.x,p.y-1));
 ...
}

Автор: math64 24.10.2011, 20:22

Так нельзя - зациклишься.
Если делать перебор, начиная движения вниз, то:
1. делаем движение вниз;
2. попадаем в тупик; вызвращаемся вверх;
3. теперь опять путь вниз свободен - движемся вниз; ...

При движении по правилу правой руки программируется примерно так:

Код


class labirint
{
public:
  class position
  {
  public:
    bool is_exit() { return x==0 || y==0 || x==width-1 || y == height-1; }
    bool step() {
      for (int rel_angle = -1; rel_angle <= 1; rel_angle++) {
        if (try_rel(rel_angle)) return go((rel_angle+angle)&3);
      }
      return false;
    }
    bool try_rel(int rel_angle) {
      return try_abs((rel_angle+angle)&3);
    }
    bool try_abs(int abs_angle) {
      if (is_exit() ) return false;
      switch(abs_angle&3) {
        case 0: return l->cells[x][y+1] != '#';
        case 1: return l->cells[x+1][y] != '#';
        case 2: return l->cells[x][y-1] != '#';
        case 3: return l->cells[x-1][y] != '#';
      }
      return false;
    }
    bool go(int abs_angle) {
      if (is_exit() ) return false;
      if"(!try_abs(abs_angle)) return false;
      switch(abs_angle&3) {
        case 0: y++; break;
        case 1: x++; break;
        case 2: y--; break;
        case 3: x--; break;
      }
      angle = abs_angle;
      return true;
    }
  private:
    int x, y, angle;
    labirint* l;
  };
private:
  char cells[width][height];
};

Но и в этом случае возможны зацикливания - если в лабиринте есть внунтенние циклы.

Автор: ShadowC 24.10.2011, 23:35

Цитата(math64 @ 24.10.2011, 20:22)

Код


class labirint
{
public:
  class position
  {
  public:
    bool is_exit() { return x==0 || y==0 || x==width-1 || y == height-1; }
    bool step() {
      for (int rel_angle = -1; rel_angle <= 1; rel_angle++) {
        if (try_rel(rel_angle)) return go((rel_angle+angle)&3);
      }
      return false;
    }
    bool try_rel(int rel_angle) {
      return try_abs((rel_angle+angle)&3);
    }
    bool try_abs(int abs_angle) {
      if (is_exit() ) return false;
      switch(abs_angle&3) {
        case 0: return l->cells[x][y+1] != '#';
        case 1: return l->cells[x+1][y] != '#';
        case 2: return l->cells[x][y-1] != '#';
        case 3: return l->cells[x-1][y] != '#';
      }
      return false;
    }
    bool go(int abs_angle) {
      if (is_exit() ) return false;
      if"(!try_abs(abs_angle)) return false;
      switch(abs_angle&3) {
        case 0: y++; break;
        case 1: x++; break;
        case 2: y--; break;
        case 3: x--; break;
      }
      angle = abs_angle;
      return true;
    }
  private:
    int x, y, angle;
    labirint* l;
  };
private:
  char cells[width][height];
};

Но и в этом случае возможны зацикливания - если в лабиринте есть внунтенние циклы.

издиваешься? в условии задачи 1 функция котоая принимает двумерный массив и отправную точку и все

Автор: baldina 25.10.2011, 01:50

надо еще текущее направление хранить, иначе непонятно куда поворачивать

http://codepad.org/hXSmuTj8
писал наспех, но идея думаю понятна

Автор: math64 25.10.2011, 07:13

Цитата(baldina @ 25.10.2011, 01:50

)

надо еще текущее направление хранить, иначе непонятно куда поворачивать

Ну я о том и говорю - в классе position есть поле angle - если не устраивает решение с классами, разверните классы в обычные функции и будет вам счастье.

Автор: ShadowC 25.10.2011, 15:54

Цитата(math64 @ 25.10.2011, 07:13)

Цитата(baldina @ 25.10.2011, 01:50

)

надо еще текущее направление хранить, иначе непонятно куда поворачивать

в том-то и прикол что по условию задания должна быть 1 функция,я думаю это не просто так...

Автор: baldina 25.10.2011, 16:29

ShadowC, теперь с условием выхода прояснилось?

Автор: ShadowC 25.10.2011, 17:45

Цитата(baldina @ 25.10.2011, 16:29)

ShadowC, теперь с условием выхода прояснилось?

да так-то оно понятно,остается невыполненным одно условие задачи,которое я думаю там нелишнее,функция должна быть одна и принимать отправную точку и массив 12-12,я думаю вся сложность в выполнение именно этого условия

Автор: baldina 25.10.2011, 17:51

а что в моем примере не так? массив и точка передается в параметрах

Автор: ShadowC 25.10.2011, 18:28

Цитата(baldina @ 25.10.2011, 17:51)

а что в моем примере не так? массив и точка передается в параметрах

я полагаю точка это не координаты,а сама точка тоесть в данном примере x[2][0] ну и у тебя 2 функции

Автор: math64 25.10.2011, 21:02

Можно рекурсию свернуть в цикл, принт реализовать внутри функции - и будет одна функция.

Код


#define N 12
#define M 12
int findPath(char maze[M][N], int x, int y) {
  int dir, exit, entry, turn, nextdir, nextx, nexty;
  char ch;
  entry = 1;
  exit = 0;
  dir = 0;
  while(!exit) {
     for (turn = - 1; turn <= 2; turn++) {
       nextdir = (dir + turn) & 3;
       switch (nextdir) {
         case 0: nextx = x; nexty = y - 1; break;
         case 1: ...; break;
         case 2: ...; break;
         case 3: ...; break;
       }
       if (maze[nextx][nexty] != '#') {
         x = nextx;
         y = nexty;
         dir = nextdir;
         ch = "^<v>"[dir];
         if (maze[x][y] == ch) {
           printf ("зацикливание - правило правой руки не работает\n");
           return 0;
         } 
         maze[x][y] = ch;
         entry = 0;
         printf(...);
         if (x == 0 || y == 0 || x == M-1 || y == N-1)
          exit = 1;
         break;
       }
     }
     if (entry) {
       printf("ходов нет - замурован\n");
       return 0;
     } 
  }
  return 1;
}

Добавлено через 5 минут и 4 секунды
Если не нравится начальную точку передавать координатами в параметрах - можно передать крестиком на карте лабиринта.
Тогда надо в начале функции добавить цикл по поиску крестика. Будет один параметр - карта лабиринта

Автор: baldina 25.10.2011, 22:40

Цитата(ShadowC @ 25.10.2011, 18:28

)

у тебя 2 функции

вторая функция (print) к алгоритму отношения не имеет, ее можно просто выбросить. к тому же она вызывается лишь раз, ее тело можно встроить в функцию maze.

Цитата(ShadowC @ 25.10.2011, 18:28

)

я полагаю точка это не координаты,а сама точка тоесть в данном примере x[2][0]

я всегда думал, что точка характеризуется координатами, а не тем, что в ней находится. например клетка на шахматной доске определяется координатами а не цветом (цвета всего 2, клеток 64).
если дело в количестве аргументов функции, заведите struct Point { int y, z; };

можно и так

Цитата(math64 @ 25.10.2011, 21:02

)

Если не нравится начальную точку передавать координатами в параметрах - можно передать крестиком на карте лабиринта.
Тогда надо в начале функции добавить цикл по поиску крестика. Будет один параметр - карта лабиринта

но это имхо параноидальное решение)))))

ShadowC, кажется Вы слишком придираетесь)))) А как ведь начиналось:

Цитата(ShadowC @ 24.10.2011, 18:13

)

только как реализовать рекурсивную функцию используя это в голову не приложу,а самое главное,я не могу понять как выйти

Автор: newbee 26.10.2011, 00:23

math64, baldina, имхо вы делаете человеку медвежью услугу. Суть передали, зачем досконально код писать, пусть сам думает. Думать - полезно.

Автор: Lols 26.10.2011, 01:43

Так что, получилась одна функция или нет?

Автор: math64 26.10.2011, 07:22

Цитата(newbee @ 26.10.2011, 00:23

)

math64, baldina, имхо вы делаете человеку медвежью услугу. Суть передали, зачем досконально код писать, пусть сам думает. Думать - полезно.

Проще написать код - чем описать как он работает. В моём коде есть ошибки - я его не запускал даже на компиляцию, пусть ищет, пишет комментарии.

Автор: baldina 26.10.2011, 10:44

Цитата(newbee @ 26.10.2011, 00:23

)

Суть передали, зачем досконально код писать, пусть сам думает. Думать - полезно.

Моск у всех по-разному устроен. Не всегда то, что одному очевидно, является простым для другого.
Бывает, что на анализ предоставленного кода человек тратит значительные усилия, а сам написать вообще не может.

Мы не сразу код начали писать.

Добавлено через 4 минуты и 36 секунд
моей первой книгой в области информатики были "Алгоритмы и структуры данных" Н.Вирта. тогда это была чуть ли не единственная книга про алгоритмы в магазине.
при первом прочтении я ничего не понял. при втором понял все. при третьем осознал, что во второй все понял неправильно.