1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include "maze_solver.h"
#include <string.h>
#include "utilities.h"
struct solver_data
{
struct maze *maze;
struct point *first_point;
struct point *last_point;
int count;
//int temp[51][51];
int **temp;
};
static void get_neighbours(struct point point, struct point *neighbours)
{
neighbours[0].x = point.x + 1;
neighbours[0].y = point.y;
neighbours[1].x = point.x - 1;
neighbours[1].y = point.y;
neighbours[2].x = point.x;
neighbours[2].y = point.y + 1;
neighbours[3].x = point.x;
neighbours[3].y = point.y - 1;
}
static int solve_maze_rec(struct solver_data *data, struct point point)
{
if (data->first_point == NULL)
data->count++;
else
*(data->last_point++) = point;
data->temp[point.x][point.y] = 1;
if (data->maze->end_point.x == point.x && data->maze->end_point.y == point.y)
{
if (data->first_point == NULL)
return data->count;
else
return (data->last_point - data->first_point);
}
struct point neighbours[4];
get_neighbours(point, neighbours);
for (int i = 0; i < 4; i++)
{
if (neighbours[i].x >= 0 &&
neighbours[i].y >= 0 &&
neighbours[i].x < data->maze->width &&
neighbours[i].y < data->maze->height &&
data->maze->map[neighbours[i].x][neighbours[i].y] != 1 &&
data->temp[neighbours[i].x][neighbours[i].y] != 1)
{
int value = solve_maze_rec(data, neighbours[i]);
if (value >= 0)
return value;
}
}
if (data->first_point == NULL)
data->count--;
else
data->last_point--;
return -1;
}
int solve_maze(struct maze *maze, struct point point, struct point *path)
{
struct solver_data solver_data;
solver_data.maze = maze;
solver_data.first_point = path;
solver_data.last_point = path;
solver_data.count = 0;
int length = sizeof_2d(maze->width, maze->height, sizeof(int));
char mem[length];
memset(mem, 0, length);
init2d((void **)mem, maze->width, maze->height, sizeof(int));
solver_data.temp = (int **)mem;
return solve_maze_rec(&solver_data, point) - 1;
}
|
