所以我必须扫描一个mazef文件,行数和列数来查找文件,有点我明白了。文件具有这样的形式
3
4
....
.#.#
....
其中第一个数字是行数,第二个数字是列数。字符“#”是一堵墙,我不能去那里,但我可以穿过“。”现在,我必须使用结构和指针找到迷宫中任意点的最短路径。示例结构在我的代码(单元格)中。我不知道该怎么做。我创建了一个``访问''数组来跟踪我去过的单元格并检查点是否有效,因此我不得不指向北,西,东,南方向的其他点。我真的需要他的帮助。
#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;
}
您可以使用[dijkstra算法](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm]查找最短路径。
因此,假设您必须返回从起点到迷宫中每个点的路径。
您具有here Dijkstra算法的实现。
您需要将其调整为您的迷宫贴图。
您可以使用结构矩阵,其中每个结构都包含前一个节点的x,y坐标,到起始节点的距离以及完成的标志。
好吧,我做了这样的事情。但是由于某种原因,它不起作用。`
#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;
}
`