Проведите лабиринт, чтобы добраться от источника к цели

Question

Я пытаюсь реализовать решение проблемы, в которой мне нужно найти путь в лабиринте рекурсивно от источника к цели.

Пусть это лабиринт: S X X X X X . . . . . X X . X X X X X . X X X X . . . X . G X X . . . X где

Х- блокировали путь

.- Открытый путь

S-Start

G -Goal

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

Мое решение

#include<iostream> 
using namespace std; 
void printGrid(char grid[6][6]) 
{ 
    for(int i=0;i<6;i++) 
    { 
     for(int j=0;j<6;j++) 
     { 
      cout<<grid[i][j]<<" "; 
     } 
     cout<<"\n"; 
    } 
} 

bool isValidPoint(char grid[6][6],int x,int y) 
{ 
    if(x<0 || x>5 || y<0 || y>5) 
    { 
     return false; 
    } 
    if(grid[x][y]=='X') 
    { 
     return false; 
    } 
    return true; 
} 

bool traceMaze(char grid[6][6],int x,int y) 
{ 
    if(!isValidPoint(grid,x,y)) 
    { 
     return false; 
    } 
    if(grid[x][y]=='G') 
    { 
     return true; 
    } 

    grid[x][y] = '+'; 

    if(traceMaze(grid,x-1,y)){return true;} 
    if(traceMaze(grid,x,y+1)){return true;} 
    if(traceMaze(grid,x+1,y)){return true;} 
    if(traceMaze(grid,x,y-1)){return true;} 

    grid[x][y] = '.'; 

    return false; 

} 


int main() 
{ 
    char grid[6][6] = {{'S','X','X','X','X','X'},{'.','.','.','.','.','X'},{'X','.','X','X','X','X'},{'X','.','X','X','X','X'},{'.','.','.','X','.','G'},{'X','X','.','.','.','X'}}; 
    cout<<"Initial grid is as follows :\n"; 
    printGrid(grid); 
    cout<<"\nStarting at : (0,0)\nTracing the path to the Goal\n"; 
    cout<<traceMaze(grid,0,0)<<"\n"; 
    cout<<"\nFinal grid is as follows :\n"; 
    printGrid(grid); 
    return 0; 
} 

PS: Я предполагаю, что размер лабиринта быть 6X6 ...

Correct Solution : 

я не имел никакого чек для '+', что я пробивался, чтобы увидеть последний прослеживаемый путь.

Так что теперь я применил чек там и функция isValidPoint превращается в:

bool isValidPoint(char grid[6][6],int x,int y) 
{ 
    if(x<0 || x>5 || y<0 || y>5) 
    { 
     return false; 
    } 
    if(grid[x][y]=='X' || grid[x][y]=='+') 
    { 
     return false; 
    } 
    return true; 
} 

Благодарим Вас за помощь, ребята :)

Я получил этот вопрос полное время интервью в прошлом году.

Answer 1

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

Простейшим решением было бы не обрабатывать и указывать с ним «+» в качестве действительной точки для входа (как вы уже были на этом пути).

Answer 2

Ответ на Темный действителен, на мой взгляд.

Ваш поиск начинается от 0,0. Затем он переходит в 0,1, а оттуда возвращается к 0,0, а затем к 0,1 ... Вы должны отметить квадраты, которые вы уже посетили, и не заходить туда снова. «+» в порядке, но вы не должны очищать его, как только вы его установили, и вы должны проверить его в isValidPoint.

Answer 3

Что вы делаете, это обход в глубину лабиринта в глубину. Вы меняете . с +, чтобы отслеживать посещаемые вами точки, но после этого вы меняете их на .. Это проблема.

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

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

Один из способов решения этой проблемы - сохранить отдельный массив 6x6 для отслеживания посещенных точек. Когда вы закончите с ячейкой (т. Е. Пройдете все возможные пути из этой ячейки), пометьте ее как «посещенный» и никогда больше не посещайте посещенную ячейку.

Answer 4

Я записал ваш лабиринт на листе бумаги и попробовал алгоритм вручную, и застрял в x = 2, y = 1, где ваш алгоритм хотел вернуться к x = 1, y = 1, вернувшись к перед государством. Это состояние, конечно, переходит в вышеупомянутое состояние и создается бесконечный цикл. Важным правилом рекурсивного программирования является всегда удостовериться, что все вызовы функций имеют все пути выполнения в обратном вызове (или аналогичные)

Если вы хотите получить мяч по этому вопросу, я бы предложил вам изучить shortest path problem решение используя, например, Dijkstra's algorithm.