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?