Solving a maze with Queues

[ja3n]

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?

[ken_taiken]

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.

[ja3n]

How do I edit my question?