Sample Input File ( Save as: maze.in): ======================== 2 3 3 ~~~ ~S~ ~~

Question

Sample Input File ( Save as:  maze.in):

========================

2
3 3
~~~
~S~
~~~
5 6
~~~~~~
~XXXX~
~XS-X~
~-XX-~
~~~~~~

=======================

Sample Output File ( Save as:  maze.out):

========================

1
-1

========================

QUESTION:  

Queues have many uses. One use of a queue is that it can be used to help find the fastest way out of a maze! The queue is an integral part of a search that is more generally called a Breadth First Search. The idea is as follows. Given a starting point in a maze, travel to all places adjacent to it and mark these as being 1 step away from the start point. Then, for each of these spots that are 1 step away, try travelling to all adjacent spots that are not yet visited. Mark these as 2 spots away. Continue until one of the spots you mark is an exit! By hand, it

Explanation / Answer

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

const char BORDER = '~';
const char EMPTY = '-';
const char START = 'S';
const char BLOCK = 'X';
const int NOT_VISITED = -1;
typedef struct CoordStruct { int r, c; } Coord;
typedef struct CoordQueueStruct {
    Coord* contents;
    int cap;
    int count;
    int front;
} CoordQueue;

int shortestDistance(FILE *fin);

int main(int argc, char* argv[])
{
    FILE *fin;
    FILE *fout;
    int testCount;
    char filePath[100];
  
    // Open input file
    fin = fopen("maze.in", "r");
    if (!fin) // handle file not found error
    {
        puts("Cannot open file. Program aborted.");
        return 1;
    }
  
    // Open output file
    if (argc == 2) { fout = fopen(argv[1], "w"); }
    else
    {
        puts("Need output file name. Program aborted.");
        return 1;
    }
  
    // Find shortest distances
    fscanf(fin, "%d", &testCount);
    while (testCount--)
        fprintf(fout, "%d ", shortestDistance(fin));
  
    fclose(fout);
    fclose(fin);
    return 0;
}


void init(CoordQueue *q)
{
    q->cap = 8;
    q->contents = (Coord*)malloc(sizeof(Coord)*q->cap);
    q->count = 0;
    q->front = 0;
}

void doubleCapacity(CoordQueue *q)
{
    int newCap = 2*q->cap;
    Coord* newContents = (Coord*)malloc(sizeof(Coord)*newCap);
    int i = 0;
    while (i < q->count)
        newContents[i++] = q->contents[(q->front++)%q->cap];
    q->front = 0;
    free(q->contents);
    q->cap = newCap;
    q->contents = newContents;
}

void enqueue(CoordQueue *q, int r, int c)
{
    if (q->count == q->cap) doubleCapacity(q);
    Coord p;
    p.r = r, p.c = c;
    q->contents[(q->front + q->count) % q->cap] = p;
    ++q->count;
}

void dequeue(CoordQueue *q, int *r, int *c)
{
    if (r) *r = q->contents[q->front].r;
    if (c) *c = q->contents[q->front].c;
    if (++q->front >= q->cap) q->front -= q->cap;
    --q->count;
}

int getNonWhiteSpaceChar(FILE *fin)
{
    int c = fgetc(fin);
    while (isspace(c)) c = fgetc(fin);
    return c;
}

int shortestDistance(FILE *fin)
{
    int row, col;
    char** maze = NULL; //maze 2D array
    int** dist = NULL; //distance 2D array
    CoordQueue q;
    int shortestDist = -1;
    int r, c;
  
    // Get maze dimensions
    fscanf(fin, "%d%d", &row, &col);
  
    // Initialize empty queue
    init(&q);
  
    // Allocate memory for maze 2D array and dist 2D array
    // Init dist 2D array NOT_VISITED
    maze = (char**)malloc(sizeof(char*)*row);
    dist = (int **)malloc(sizeof(int *)*row);
    for (r = 0; r < row; ++r)
    {
        maze[r] = (char*)malloc(sizeof(char)*col);
        dist[r] = (int *)malloc(sizeof(int) *col);
        for (c = 0; c < col; ++c) { dist[r][c] = NOT_VISITED; }
    }
  
    // Fill maze and set starting position to dist, q
    for (r = 0; r < row; ++r)
        for (c = 0; c < col; ++c)
        {
            maze[r][c] = getNonWhiteSpaceChar(fin);
            if (maze[r][c] == START)
            {
                dist[r][c] = 0;
                enqueue(&q, r, c);
            }
        }
      
    // Solve using BFS
    while (q.count)
    {
        // Retrieve the front Coord in q
        dequeue(&q, &r, &c);
      
        // If any of top, bottom, left, right square is BORDER,
        //we have reached the border, break out of the loop and set
        //shortestDist to current square distance + 1
        if (maze[r-1][c] == BORDER || maze[r+1][c] == BORDER ||
            maze[r][c-1] == BORDER || maze[r][c+1] == BORDER)
        {
            shortestDist = dist[r][c] + 1;
            break;
        }
      
        // Check top square
        if (maze[r-1][c] != BLOCK && dist[r-1][c] == NOT_VISITED)
        {
            dist[r-1][c] = dist[r][c] + 1;
            enqueue(&q, r-1, c);
        }
        // Check bottom square
        if (maze[r+1][c] != BLOCK && dist[r+1][c] == NOT_VISITED)
        {
            dist[r+1][c] = dist[r][c] + 1;
            enqueue(&q, r+1, c);
        }
        // Check left square
        if (maze[r][c-1] != BLOCK && dist[r][c-1] == NOT_VISITED)
        {
            dist[r][c-1] = dist[r][c] + 1;
            enqueue(&q, r, c-1);
        }
        // Check right square
        if (maze[r][c+1] != BLOCK && dist[r][c+1] == NOT_VISITED)
        {
            dist[r][c+1] = dist[r][c] + 1;
            enqueue(&q, r, c+1);
        }
    }
  
    // Free maze 2D array, dist 2D array, and queue q
    for (r = 0; r < row; ++r)
    {
        free(maze[r]);
        free(dist[r]);
    }
    free(maze);
    free(dist);
    free(q.contents);
  
    return shortestDist;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.