calgorithmdepth-first-searchmaze
Reaching The Goal With The Dfs Algorithm
#include <stdio.h>
char matrix[8][8];
struct coordinate {
int a;
int b;
};
void ReadFile() {
printf("\n\n\n START MAZE ");
int x, y;
FILE * file1;
file1 = fopen("NEWmaze.txt", "r");
for (x = 0; x < 8; x++) {
for (y = 0; y < 8; y++) {
fscanf(file1, " %c", & matrix[x][y]);
}
printf("\n");
}
}
void PrintMaze() {
int x, y;
for (x = 0; x < 8; x++) {
printf(" ");
for (y = 0; y < 8; y++) {
printf(" %c ", matrix[x][y]);
}
printf("\n");
}
printf("\n\n\n\n");
}
struct coordinate DFS(int x, int y) {
struct coordinate retval = {
x,
y
};
printf("%c", matrix[x - 1][y]); //saw the target but could not stop
if (matrix[x][y - 1] == '-') //WEST
{
printf("WEST");
// printf("%d %d",x,y-1); step by step
matrix[x][y - 1] = '.';
PrintMaze(); //step by step
DFS(x, y - 1);
struct coordinate retval = {
x,
y - 1
};
}
if (matrix[x][y - 2] == 'g' && matrix[x + 1][y - 2] != '#') {
// printf("%d %d ",x,y-2); step by step
return retval;
}
if (matrix[x - 1][y] == '-') //NORTH
{
// printf("%d %d",x-1,y); step by step
matrix[x - 1][y] = '.';
PrintMaze(); //step by step
DFS(x - 1, y);
struct coordinate retval = {
x - 1,
y
};
}
if (matrix[x - 2][y] == 'g' && matrix[x - 3][y] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
if (matrix[x][y + 1] == '-') //SOUTH
{
//printf("%d %d",x,y+1); step by step
matrix[x][y + 1] = '.';
PrintMaze();
DFS(x, y + 1);
struct coordinate retval = {
x,
y + 1
};
}
if (matrix[x + 1][y + 1] == 'g' && matrix[x + 2][y + 1] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
if (matrix[x + 1][y] == '-') { // EAST
// printf("%d %d",x+1,y);
matrix[x + 1][y] = '.';
//PrintMaze();
DFS(x + 1, y);
struct coordinate retval = {
x + 1,
y
};
}
if (matrix[x + 1][y + 1] == 'g' && matrix[x + 1][y + 2] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
return retval;
}
void StartSearch() {
printf(" STEP BY STEP");
int x, y;
for (x = 0; x < 8; x++) {
for (y = 0; y < 8; y++) {
if (matrix[x][y] == 's') //START
{
struct coordinate coord = DFS(x, y);
}
}
printf("\n");
}
}
int main() {
ReadFile();
PrintMaze();
StartSearch();
PrintMaze();
return 0;
}
newMaze.txt file (# wall, . step, - empty , s start,g goal)
# # # # # # # #
# g - - # - - #
# - - - - - # #
# - - # - - - #
# - - # - - # #
# - - - - - - #
# - # - - - s #
# # # # # # # #
I print the steps and i can see it reaches the goal.The only problem is it doesn't stop when i reach the goal('g').When I use while break it can't get out of infinite loops. How do I make it stop when it reaches the goal('g')?
This is a follow up to ->
Maze solver with DFS ( here i tried using struct as x and y are not returning at the same time )
UPDATE
#include <stdio.h>
char matrix[8][8];
struct coordinate {
int x, y;
};
void ReadFile()
{
printf("\n\n\n START MAZE ");
int x,y;
FILE *file1;
file1=fopen("NEWmaze.txt","r");
for(x=0; x<8; x++){
for(y=0;y<8;y++)
{
fscanf (file1, " %c", &matrix[x][y]);
}
printf("\n");
}
}
void PrintMaze()
{
int x,y;
for(x=0;x<8;x++)
{
printf(" ");
for(y=0;y<8;y++)
{
printf(" %c ",matrix[x][y]);
}
printf("\n");
}
printf("\n\n\n\n");
}
struct coordinate DFS(int x, int y)
{
struct coordinate retval = { -1, -1 };
if (matrix[x][y] == 'g')
{
retval.x = x;
retval.y = y;
}
else if (matrix[x][y] == '-' )
{
matrix[x][y] = 'o';// West North South East
PrintMaze();
retval = DFS(x, y-1); if (retval.x != -1) return retval;
retval = DFS(x-1, y ); if (retval.x != -1) return retval;
retval = DFS(x , y+1); if (retval.x != -1) return retval;
retval = DFS(x + 1, y); matrix[x][y] = '.';
}
return retval;
}
void StartSearch()
{
printf(" STEP BY STEP");
int x,y;
for(x=0;x<8;x++)
{
for(y=0;y<8;y++)
{
if(matrix[x][y] == 's')//START
{
if(matrix[x][y-1] == '-')
{
DFS(x,y-1);
}
if(matrix[x-1][y] == '-')
{
DFS(x-1,y);
}
if(matrix[x][y+1] == '-')
{
DFS(x,y+1);
}
if(matrix[x+1][y] == '-')
{
DFS(x+1,y);
}
}
}
printf("\n");
}
}
int main()
{
ReadFile();
PrintMaze();
StartSearch();
PrintMaze();
return 0;
}
UPDATE OUPUT
I wrote in order of priority and it works.
Solution
You're going about the return value in a weird way. Instead of constructing it after the recursive call, simply make it so that a valid co-ordinate is returned if the current position is the goal. Otherwise, return something invalid (e.g. {-1,-1}, or even {0,0} in your case if that will always be a wall).
Now all you need to do is store the return value of each recursive call and check if it's valid. If it is, then return it immediately. Otherwise continue processing (i.e. test other directions).
Put in terms of code, something like this:
struct coordinate {
int x, y;
};
struct coordinate DFS(int x, int y)
{
struct coordinate retval = { -1, -1 };
if (matrix[x][y] == 'g')
{
retval.x = x;
retval.y = y;
}
else if (matrix[x][y] == '-' || matrix[x][y] == 's')
{
matrix[x][y] = '.';
retval = DFS(x - 1, y); if (retval.x != -1) return retval;
retval = DFS(x, y - 1); if (retval.x != -1) return retval;
retval = DFS(x + 1, y); if (retval.x != -1) return retval;
retval = DFS(x, y + 1);
}
return retval;
}
Provided your maze always has a wall around the perimeter, you don't need to do any bounds-testing on the co-ordinates because you will never perform recursion when on the edge.
You can even slightly reorder this to draw the actual path used when you first reached the goal. It might not be the optimal path, but that requires a more advanced algorithm. Below, we use 'o' to denote a cell on the path to the goal.
struct coordinate DFS(int x, int y)
{
struct coordinate retval = { -1, -1 };
if (matrix[x][y] == 'g')
{
retval.x = x;
retval.y = y;
}
else if (matrix[x][y] == '-' || matrix[x][y] == 's')
{
matrix[x][y] = '.';
retval = DFS(x - 1, y);
if (retval.x == -1) retval = DFS(x, y - 1);
if (retval.x == -1) retval = DFS(x + 1, y);
if (retval.x == -1) retval = DFS(x, y + 1);
if (retval.x != -1) matrix[x][y] = 'o';
}
return retval;
}
And with a small tweak to the search function:
void StartSearch()
{
int x, y;
for (x = 0; x < 8; x++) {
for (y = 0; y < 8; y++) {
if (matrix[x][y] == 's')
{
DFS(x, y);
matrix[x][y] = 's';
}
}
}
}
You get this output:
# # # # # # # #
# g o o # . . #
# - - o o o # #
# - - # - o - #
# - - # - o # #
# - - - - o o #
# - # - - - s #
# # # # # # # #
- Casting Pointer array from one type to another
- Minimizing the number of malloc() calls improves performance?
- Difference between curl/curl.h, libcurl, libcurl4-openssl-dev, libcurl4-nss-dev libraries?
- Why doesn't my manually entered double value match the expected value in C?
- From 2D Arrays to 2x2 Matrix in C
- How to determine the value of socket listen() backlog parameter?
- What does #define do in the Compiler?
- Deleting selected element in a doubly linked list
- Writing to qemu RISCV UART using c
- Bubble sort does not sort as expected
- How to store and then print a 2d character/string array horizontally for 5 times?
- Fast CRC algorithm?
- Assertion —to a function pointer— failed
- Learning c, my code runs but doesn't displayed print?
- Strange size change in core dump file
- Rust's .o file format not recognized by GCC
- How to declare a constant "mutable pointer" to an immutable block of memory
- Printing all environment variables in C / C++
- What is the difference between getch() and getchar()?
- Filemanagement in C: Unsuccessful attempt in creating/overwriting a file using fopen
- Get pixel color at mouse position fastest way
- Valid VISA: 4222222222222 outputted as invalid
- Unique Words Counter in C
- Confused about casting and order of operations
- What is the closest thing Windows has to fork()?
- Why No Variable Declarations in Boolean Expressions in C?
- Search Algorithm to find the k lowest values in a list (selection algorithm/problem)
- What is the need of hh and h format specifiers?
- can't load bmp file with SDL_LoadBMP in CodeBlocks
- Need help to solve function issue