Крыса в лабиринте

Гораздо более простой, чем вот здесь, консольный "лабиринт", описанный матрицей, в которой нули обозначают проходимые клетки, а единички - стены. Перебор выполняется нерекурсивно без каких-либо "лишних" вызовов вложенных функций. Поэтому стек этот код не переполнит, а дополнительной памяти использует N*N*3 значений, конечно, наверняка существуют алгоритмы экономичней :) Волновой подход рулит.

Если решений несколько, найдётся только первое из них. Изображает найденный путь девятками в копии sol матрицы лабиринта maze. Если пути нет, зависать не должен, а функция вернёт false вместо true.

Впрочем, код особо не "вылизывался" и публикуется по просьбе трудящегося в учебных целях.

#include <cstdio>

const int N=6; /* Размерность, для простоты одинакова по обеим осям координат */

int maze[N][N] = { //Лабиринт
 { 0, 1, 1, 1, 1, 1 },
 { 0, 0, 0, 0, 0, 1 },
 { 1, 0, 1, 1, 0, 1 },
 { 1, 0, 0, 0, 0, 0 },
 { 1, 1, 0, 1, 0, 1 },
 { 1, 0, 0, 0, 0, 0 }
};

int sol[N][N]; //Решение

void printSolution() { //Вывод решения
 printf("\nMaze:\n");
 for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) printf(" %d ", maze[i][j]);
  printf("\n");
 }
 printf("\nSolution:\n");
 for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) printf(" %d ", sol[i][j]);
  printf("\n");
 }
}

bool SearchWay (int x, int y, int x_to, int y_to) {
 int matrix[N][N][3];
 int step;
 bool added = true, result = true;
 for (int i = 0; i<N; i++) {
  for (int j = 0; j<N; j++) {
   if (maze[i][j] != 0) {
    matrix[i][j][0] = -2;// занято
   }
   else  {
    matrix[i][j][0] = -1;// Мы еще нигде не были
   }
  }
 }
 matrix[x_to][y_to][0] = 0;// До финиша ноль шагов - от него будем разбегаться
 step = 0; // Изначально мы сделали ноль шагов
 while (added && matrix[x][y][0] == -1) { //Пока вершины добавляются и не дошли до старта
  added = false;// Пока что ничего не добавили
  step++;// Увеличиваем число шагов
  for (int i = 0; i<N; i++) { // Пробегаем по всей карте
   for (int j = 0; j<N; j++) {
    //Если (i, j) была добавлена на предыдущем шаге, пробегаем по всем четырем сторонам
    if (matrix[i][j][0] == step - 1) {
     int _i, _j;
     _i = i + 1; _j = j;
     
     if (_i >= 0 && _j >= 0 && _i<N && _j<N) { //Если не вышли за пределы карты - обрабатываем
      if (matrix[_i][_j][0] == -1 && matrix[_i][_j][0] != -2) {
       //Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
       matrix[_i][_j][0] = step; // Добавляем
       matrix[_i][_j][1] = i; 
       matrix[_i][_j][2] = j; 
       added = true; // Что-то добавили
      }
     }
     _i = i - 1; _j = j;
     if (_i >= 0 && _j >= 0 && _i<N && _j<N) { //Если не вышли за пределы карты - обрабатываем
      if (matrix[_i][_j][0] == -1 && matrix[_i][_j][0] != -2) {
       //Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
       matrix[_i][_j][0] = step; // Добавляем
       matrix[_i][_j][1] = i;
       matrix[_i][_j][2] = j;
       added = true; // Что-то добавили
      }
     }
     _i = i; _j = j + 1;
     if (_i >= 0 && _j >= 0 && _i<N && _j<N) { //Если не вышли за пределы карты - обрабатываем
      if (matrix[_i][_j][0] == -1 && matrix[_i][_j][0] != -2) {
       //Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
       matrix[_i][_j][0] = step; // Добавляем
       matrix[_i][_j][1] = i;
       matrix[_i][_j][2] = j;
       added = true; // Что-то добавили
      }
     }
     _i = i; _j = j - 1;
     
     if (_i >= 0 && _j >= 0 && _i<N && _j<N) { //Если не вышли за пределы карты - обрабатываем
      
      if (matrix[_i][_j][0] == -1 && matrix[_i][_j][0] != -2) {
       //Если (_i, _j) уже добавлено или непроходимо, то не обрабатываем 
       matrix[_i][_j][0] = step; // Добавляем
       matrix[_i][_j][1] = i;
       matrix[_i][_j][2] = j;
       added = true; // Что-то добавили
      }
     }
    }
   }
  }
 }

 if (matrix[x][y][0] == -1) {
  result = false; //то пути не существует
 }
 if (result) {
  int _i = x, _j = y;
  while (matrix[_i][_j][0] != 0) {
   int li = matrix[_i][_j][1];
   int lj = matrix[_i][_j][2];
   _i = li; _j = lj;
   //код, где записываем значение клеток и шагаем дальше к началу, записывать надо _i , _j :
   sol[_i][_j] = 9;
  }
 }
 return result;
}

int main() {
 for (int i = 0; i < N; i++)
 for (int j = 0; j < N; j++) sol[i][j] = maze[i][j];
 
 int startRow = 0, startCol = 0, endRow = 5, endCol = 5; //Откуда и куда идём
 sol[startRow][startCol] = 9; //Один шаг уже сделан :)

 bool r = SearchWay(startRow, startCol, endRow, endCol);
 if (r) printSolution();
 else printf ("\nNo solution!");
 getchar();
 return 0;
}

Вывод примера из этого кода, выполненного в консоли Visual Studio 2015:

Maze:
 0  1  1  1  1  1
 0  0  0  0  0  1
 1  0  1  1  0  1
 1  0  0  0  0  0
 1  1  0  1  0  1
 1  0  0  0  0  0

Solution:
 9  1  1  1  1  1
 9  9  9  9  9  1
 1  0  1  1  9  1
 1  0  0  0  9  0
 1  1  0  1  9  1
 1  0  0  0  9  9

09.09.2018, 15:26 [2253 просмотра]