Hi, I am trying to solve a maze using queues(no recursion)

What I've done so far is that I can figure out whether or not the maze can be solved. What my next step should be is to list out STEP BY STEP how the maze will be solved. For example:

``````#######
#...#o#
#*#...#
#######
[2,1][1,1][1,2][1,3][2,3][2,4][2,5][1,5]
``````
= wall, *=finish, o=start

This is how i check if a maze can be solved.

``````#include <stdio.h>
#include <stdlib.h>
#include "QueueInterface.h"

int main(void){
char file[1024];
fgets(file, 1024, stdin);
Queue Q;
InitializeQueue(&Q);

//Getting number of rows and columns
int row, col, i, j;
sscanf(file, "%d %d", &col, &row);
printf("%d %d\n", col, row);

//Putting maze into 2d array
ItemType maze[500][500];
for(i=0;i<row;i++){
fgets(file, 1024, stdin);
for(j=0;j<col;j++){
maze[i][j].ch=file[j];
maze[i][j].x=i;
maze[i][j].y=j;
}
}

//Finding the start square
int trow, tcol;
for(i=0;i<row ;i++)
for(j=0;j<col;j++)
if ( maze[i][j].ch=='o'){
trow=i;
tcol=j;
}

//Putting the start square into the queue
Insert(maze[trow][tcol], &Q);
ItemType temp;
int finish=0;
int tx, ty;

//Removing ItemTypes from the Queue and looking in 4 directions to see if there is a non-wall space
while(!Empty(&Q)){
Remove(&Q, &temp);
tx=temp.x;
ty=temp.y;
if(!temp.visited){
if(temp.ch=='*'){
finish=1;
break;
}
else
{
if (maze[tx+1][ty].ch=='*' || maze[tx+1][ty].ch=='.')Insert(maze[tx+1][ty], &Q);
if (maze[tx-1][ty].ch=='*' || maze[tx-1][ty].ch=='.')Insert(maze[tx-1][ty], &Q);
if (maze[tx][ty+1].ch=='*' || maze[tx][ty+1].ch=='.')Insert(maze[tx][ty+1], &Q);
if (maze[tx][ty-1].ch=='*' || maze[tx][ty-1].ch=='.')Insert(maze[tx][ty-1], &Q);

}
maze[tx][ty].visited=1;
}
}

//printing the maze
for(i=0;i<row;i++)
for(j=0;j<col;j++){
printf("%c", maze[i][j].ch);
if(j==(col-1))
printf("\n");
}
//Was there a solution?
if (finish==1){
printf("A Solution \n");

}
else
printf("No Solution \n");
}
``````

Itemtype basically describes the maze square

``````#include <stdio.h>
#include <stdlib.h>

typedef struct ItemType {
int visited, x, y;
char ch;
}ItemType;
``````

There are other methods that are used such as Queue.c and QueueInterface.h.

Any ideas on how to find the steps to solve a maze?

I think adding extra attributes to hold the parent's or ancestor's position in a cell will help.

Every time before you add adjacent cells to the queue, set the values for the parent's co-ordinates of each valid adjacent node to that of the current cell's co-ordinates. If there's a solution, you can then start from the finish and go along the parent's co-ordinates recursively or iteratively until you reach the source. This will help you get a path.

How do I edit my question?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.