Программа поиска пути с использованием рекурсивной функции в c - PullRequest
Новая
       19

Программа поиска пути с использованием рекурсивной функции в c

1 голос
/ 06 марта 2020

Мне нужно написать программу C, чтобы найти кратчайший путь от 0x0 до mxn (для простоты здесь я назову эти точки S для Начало и E для конца) точка в 2d массиве с использованием рекурсивной функции . Но я не знаю никаких алгоритмов, я просто очень мало знаю и знаю c вещи о C, и я не знаю, как и с чего начать. Я провел несколько исследований и написал что-то вроде этого, но у него есть две основные проблемы: 1) он не возвращается , 2) он не перемещается автоматически. Я хочу использовать рекурсию для автоматического перемещения, но я не смог этого сделать. 

#include <stdio.h>
#include <stdbool.h>
#define N 6
/// For printing the final solution Matrix
void printSolution(int solution[N][N]){
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", solution[i][j]);
        printf("\n");
    }
}
/// For checking if solution coordinate is in matrix or not
bool isSafe(int maze[N][N], int x, int y){
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;
    return false;
}
/// For looking to the neighbour cells
bool lookRight(int maze[N][N], int x, int y){
    if(maze[x][y+1]==0)
        return false;
    if(maze[x][y+1]==1)
        return true;
}
bool lookDown(int maze[N][N], int x, int y){
    if(maze[x+1][y]==0)
        return false;
    if(maze[x+1][y]==1)
        return true;
}
bool lookLeft(int maze[N][N], int x, int y){
    if(maze[x][y-1]==0)
        return false;
    if(maze[x][y-1]==1)
        return true;
}
bool lookUp(int maze[N][N], int x, int y){
    if(maze[x-1][y]==0)
        return false;
    if(maze[x-1][y]==1)
        return true;
}
/// For moving in available direction
bool moveRight(int maze[N][N], int x,int y){
    if (lookRight(maze, x, y)==true && isSafe(maze, x, y)==true)
        return true;
    else
        return false;
}
bool moveDown(int maze[N][N], int x,int y){
    if (lookDown(maze, x, y)==true && isSafe(maze, x, y)==true)
        return true;
    else
        return false;
}
bool moveLeft(int maze[N][N], int x,int y){
    if (lookLeft(maze, x, y)==true && isSafe(maze, x, y)==true)
        return true;
    else
        return false;
}
bool moveUp(int maze[N][N], int x,int y){
    if (lookUp(maze, x, y)==true && isSafe(maze, x, y)==true)
        return true;
    else
        return false;
}
/// For solving the main maze
bool solveMaze(int maze[N][N], int x, int y, int xFinal, int yFinal){
    int solution[N][N]={{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},
                        {0, 0, 0, 0, 0, 0}};
    if (moveRight(maze, x, y)==true){
        solution[x][y+1]=1;
    }
    if (moveDown(maze, x, y)==true){
        solution[x+1][y]=1;
    }
    if (moveLeft(maze, x, y)==true){
        solution[x][y-1]=1;
    }
    if (moveUp(maze, x, y)==true){
        solution[x-1][y]=1;
    }
    printSolution(solution);
}
/// Main maze
int main() {         //S
    int maze[N][N] = {{1, 0, 1, 1, 1, 1},
                      {1, 0, 1, 0, 0, 1},
                      {1, 0, 1, 0, 0, 1},
                      {1, 0, 1, 0, 0, 1},
                      {1, 1, 1, 0, 0, 1},
                      {0, 0, 0, 0, 0, 1}};
    solveMaze(maze, 0, 0, N, N);    //E
    return 0;}

Моя главная цель в этой программе - найти кратчайший доступный путь к go из, Начало до Конец . Мне нужно использовать рекурсивную функцию, чтобы иметь возможность перемещаться и искать пути. Но в этом коде я могу только вручную ввести каждую точку, чтобы проверить все остальные части. Например: 

 int main() {
    int maze[N][N] = { {1, 0, 1, 1, 1, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 1, 1, 0, 0, 1},
                       {0, 0, 0, 0, 0, 1} };
    solveMaze(maze, 2, 2, N, N);
    return 0;
}

здесь, мой ввод - это элемент (2, 2) (Почему я дал (2,2) вместо (0,0), потому что я хотел показать лучше, в готовой программе это начнется с 0x0 пункта или S для краткости) . 

{ {1, 0, 1, 1, 1, 1},
  {1, 0, 1, 0, 0, 1},
  {1, 0, (1), 0, 0, 1}, // by element(2, 2) I mean this (1) in here
  {1, 0, 1, 0, 0, 1},
  {1, 1, 1, 0, 0, 1},
  {0, 0, 0, 0, 0, 1} }

Сначала он проверит свое право, это 0, поэтому он ничего не будет делать. Далее он проверит, это 1, поэтому он изменит 0 на 1 в матрице решения. Я думаю, что теперь все ясно, поэтому вывод для этого ввода будет выглядеть следующим образом: 

 0  0  0  0  0  0
 0  0  1  0  0  0
 0  0  0  0  0  0
 0  0  1  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0

Это был ввод вручную, но я хочу, чтобы он мог перемещаться автоматически, здесь 1 - это путь, а 0 это стена. 

int main() {
    int maze[N][N] = { {S, 0, 1, 1, 1, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 1, 1, 0, 0, E} };
    solveMaze(maze, 2, 2, N, N);
    return 0;
}

Она должна начинаться с S и должна заканчиваться на E, и мне нужно написать функцию для этого, пока она не достигнет E.

Вторая проблема - это не возвращайтесь, например: 

int main() {
    int maze[N][N] = { {S, 0, 1, 1, 1, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 0, 1, 0, 0, 1},
                       {1, 1, 1, X, 0, 1},
                       {0, 0, 0, 0, 0, E} };
    solveMaze(maze, 2, 2, N, N);
    return 0;
  }

здесь моя программа будет go к X (X здесь только 1 в матрице, я написал X, чтобы показать вам, что именно я значит) сначала (, если мы считаем, что первая проблема решена и она может двигаться автоматически ), затем она проверит своих четырех соседей, и все они равны 0. То, что я хочу, это возврат до 1, затем возобновить оттуда. Если все правильно, он должен двигаться вверх, и результат должен выглядеть так: 

 S  0  1  1  1  1
 1  0  1  0  0  1
 1  0  1  0  0  1
 1  0  1  0  0  1
 1  1  1  0  0  1
 0  0  0  0  0  E

, а не так: 

 S  0  0  0  0  0
 1  0  0  0  0  0
 1  0  0  0  0  0
 1  0  0  0  0  0
 1  1  1  1  0  0
 0  0  0  0  0  E

Это оригинальный вопрос

...