Кратчайший путь в любую точку лабиринта

Question

Так что мне нужно сканировать лабиринт по числу строк и столбцов для файла, но я получил эту часть.

Файл имеет такую ​​форму

3
4
....
.#.#
....

Где первое число количество строк, а второе число столбцов. Символ «#» - это стена, и я не могу go там, но я могу go через «.» Теперь я должен, используя структуры и указатели, найти кратчайший путь к любой точке лабиринта. Пример структуры в моем коде (Cell).

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

Каким-то образом я должен указывать на другие точки в СЕВЕ, ЗАПАДЕ, ВОСТОК, ЮГ. направления.

#include "stdafx.h"
#include "stdlib.h"

//Starting point
#define START_X 0
#define START_Y 0

//example structure I have to use
struct Cell
{
    struct Cell *north;
    struct Cell *east;
    struct Cell *south;
    struct Cell *west;
    char value;
    int distance;
};

//function that prints a maze
void printMap(char **charMaze, int row, int col)
{

    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            printf_s("%c", charMaze[i][j]);
        }
        printf_s("\n");
    }

}

// functions that check if a point is valid
bool isValid(int x, int y, int row, int col)
{
    if (x < row && y < col && x >= 0 && y >= 0)
        return true;

    return false;
}

bool isSafe(char **charMaze, int **visited, int x, int y)
{
    if (charMaze[x][y] == '#' || visited[x][y]==true)
        return false;

    return true;
}

//My attempt at solving this
int BFS(char **maze,int END_X, int END_Y,int row, int col, bool **visited)
{
    isValid(END_X, END_Y, row, col);    
}

int main()
{

    FILE *map;
    int row, col;

    // I open a file with a maze
    fopen_s(&map, "test1.txt", "r");
    // I scan a row number and column number
    fscanf_s(map, "%d", &row);
    fscanf_s(map, "\n%d\n", &col);

    char** charMaze;
    charMaze = (char**)malloc(row * sizeof(char*));

    for (int i = 0; i < row; i++)
        charMaze[i] =(char*)malloc(col * sizeof(char));

    bool** visited;
    visited = (bool**)malloc(row * sizeof(bool*));

    for (int i = 0; i < row; i++)
        visited[i] = (bool*)malloc(col * sizeof(bool));
    //set staring point as true and other points as false
    visited[START_X][START_Y] = true;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            visited[i][j] = false;
        }
    }
    // I scan a maze and I put it in a array
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            fscanf_s(map, "%c", &charMaze[i][j],1);
        }
        fscanf_s(map, "\n");
    }

    fclose(map);
    //printMap(charMaze, row, col);

    return 0;

}

Answer 1

Хорошо, я сделал что-то подобное. Но по какой-то причине это не работает.

#include "stdafx.h"
#include "stdlib.h"

//Starting point
#define START_X 0
#define START_Y 0
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

//example structure I have to use
struct Cell
{
    struct Cell *north;
    struct Cell *east;
    struct Cell *south;
    struct Cell *west;
    char value;
    int distance;


};


//function that prints a maze
void printMap(char **charMaze, int row, int col)
{

    for (int i = 0; i < row; i++)
    {

        for (int j = 0; j < col; j++)
        {
            printf_s("%c", charMaze[i][j]);
        }
        printf_s("\n");
    }

}

void printMap2(int **intMaze, int row, int col)
{

    for (int i = 0; i < row; i++)
    {

        for (int j = 0; j < col; j++)
        {
            printf_s("%d", intMaze[i][j]);
        }
        printf_s("\n");
    }

}

// functions that check if a point is valid
bool isValid(int x, int y, int row, int col)
{
    if (x < row && y < col && x >= 0 && y >= 0)
    {

        printf("Dobry punkt");
        return true;
    }
    else
    {
        printf("Nieprawidlowy");
    }

    return false;
}

bool isSafe(char **charMaze, int **visited, int x, int y)
{
    //char wall = '#';
    //char character = charMaze[x][y];
    if (charMaze[x][y] =='#' || visited[x][y])
    {

        printf("unsafe");
        return false;
    }
    else
    {
        printf("safe");
    }

    return true;
}

bool canGo(Cell *cell, int d)
{
    if (cell == NULL)
    {
        return 0;
    }
    if (cell->value == '#')
        return 0;
    if (cell->value == '.')
        return 1;
    if (cell->distance > d)
        return 1;

        return 0;
}

void findShortestPath(char **maze, int start_X, int start__Y, int i, int j, int row, int col, int **visited, int minDist, int dist)
{
    if (j = start__Y && i == start_X)
    {
        minDist = MIN(dist, minDist);
        return;
    }
    visited[start_X][start__Y] = 1;

    //bottom
    if (isValid(start_X + 1, start__Y, row, col) && isSafe(maze, visited, start_X + 1, start__Y))
        findShortestPath(maze, start_X + 1, start__Y, i, j, row, col, visited, minDist, dist + 1);
    //right
    if (isValid(start_X, start__Y + 1, row, col) && isSafe(maze, visited, start_X, start__Y + 1))
        findShortestPath(maze, start_X, start__Y + 1, i, j, row, col, visited, minDist, dist + 1);
    //top
    if (isValid(start_X - 1, start__Y, row, col) && isSafe(maze, visited, start_X + 1, start__Y))
        findShortestPath(maze, start_X + 1, start__Y, i, j, row, col, visited, minDist, dist + 1);
    //left
    if (isValid(start_X, start__Y - 1, row, col) && isSafe(maze, visited, start_X, start__Y - 1))
        findShortestPath(maze, start_X, start__Y - 1, i, j, row, col, visited, minDist, dist + 1);
    visited[start_X, start__Y] = 0;

}

int main()
{
    FILE *map;
    int start_X = 0;
    int start_Y = 0;
    int row, col;
    struct Cell cell;
    // I open a file with a maze
    fopen_s(&map, "test1.txt", "r");
    // I scan a row number and column number
    fscanf_s(map, "%d", &row);
    fscanf_s(map, "\n%d\n", &col);


    char** charMaze;
    charMaze = (char**)malloc(row * sizeof(char*));

    for (int i = 0; i < row; i++)
        charMaze[i] = (char*)malloc(col * sizeof(char));

    int** visited;
    visited = (int**)malloc(row * sizeof(int*));

    for (int i = 0; i < row; i++)
        visited[i] = (int*)malloc(col * sizeof(int));

    memset(visited, 0, sizeof visited);
    int minDist = INT_MAX;

    // I scan a maze and I put it in a array
    for (int i = 0; i < row; i++)
    {

        for (int j = 0; j < col; j++)
        {
            fscanf_s(map, "%c", &charMaze[i][j], 1);
        }
        fscanf_s(map, "\n");
    }

    findShortestPath(charMaze, start_X, start_Y, 2, 3, row, col, visited, minDist, 0);

    if (minDist != INT_MAX)
    {
        printf("Najkrotsza droga z poczatku do konca to %d", minDist);

    }
    else
    {
        printf("Can't get to the point");
    }


    printMap(charMaze, row, col);

    fclose(map);

return 0;

}

Answer 2

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

В результате предположим, что вы должны вернуть путь от начальной точки к каждой точке в лабиринте.

У вас есть здесь реализация алгоритма Дейкстры.

Вы должны адаптировать свою карту лабиринта.

Вы можете использовать матрицу структур, где каждая структура содержит координаты x, y предыдущего узла, расстояние до начального узла, и флаг готов.

Редактировать

Если факт, вам даже не нужно реализовывать алгоритм Дейкстры. Простой алгоритм затопления подойдет, потому что вес всех вершин графа равен единице.

Вот как бы я это сделал.

#include <stdbool.h>
#include <stdlib.h>


enum State { Wall, Unvisited, WaveBorder, NewWaveBorder, Done };

// define the structure holding coordinates of previous cell in path and state
typedef struct Cell {
    int i,j; // coordinates of predecessor in path
    enum State state;
} Cell; 

// visit cell (vi,vj) from neighbor cell (i,j)
void visitCell(Cell **m, int vi, int vj, int i, int j) {
    if m[vi][vj].state == Unvisited {
        m[vi][vj].state = NewWaveBorder;
        m[vi][vj].i = i;  
        m[vi][vj].j = j;
    }
}

Cell** findShortestPath(char **maze, int row, int col, int iStart, int jStart) {
    Cell **m = malloc(sizeof(Cell*)*row);
    for (int i = 0; i < row; i++)
        m[i] = malloc(sizeof(Cell)*col);
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            if (maze[i][j] == '.') {
                m[i][j].state = Unvisited;
                m[i][j].i = m[i][j].j = -1;
            } else {
                m[i][j].state = Wall;
                m[i][j].i = m[i][j].j = -2;
            }

    m[iStart][jStart].state = WaveBorder;
    bool done = false;
    while (!done) {
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                if (m[i][j].state != waveBorder)
                    continue;
                if (i > 0)
                    visitCell(m, i-1, j, i, j);
                if (j > 0)
                    visitCell(m, i, j-1, i, j);
                if (i < row)
                    visitCell(m, i+1, j, i, j);
                if (j < col)
                    visitCell(m, i, j+1, i, j);
                m[i][j].state = Done;
            }
        done = true;
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (m[i][j].state == Unvisited)
                    done = false;
                else if (m[i][j].state == NewWaveBorder)
                    m[i][j].state == WaveBorder;
    }
    return m;
}

Путь от ячейки (i, j) хранится в матрице Cell структур. Каждая ячейка имеет координаты предшественника на пути к (iStart, jStart). Ячейка (iStart, jStart) будет иметь (-1, -1) в качестве предшественника на пути. Стены будут иметь (-2, -2) в качестве предшественников.