CSSS Coding Competition

# CSSS Coding Competition -- October 2002

## Problem 4

The problem is to find the shortest path through a maze. Your program should read several mazes from the input file and write the same mazes with paths to the output file.

All non-white characters in the input file are X's. The other characters are all blanks or new lines. A maze consists of several non-blank lines followed by a blank line. The single character X following a blank line indicates the end of the input file.

Blanks in the maze correspond to paths; X's correspond to walls. Two of the lines of the maze (not the first or the last) start with a blank; these are the entrance and exit points for the maze. All other lines of the maze start with X.

The output file should be identical to the input file except that blanks have been replaced by dots to show the shortest path through the maze. The allowed steps are left, right, up, and down; diagonal moves are not allowed.

Here is a typical input file:

            XXXXXX
               X X
            X XX X
                 X
            XXXXXX

            XXXXXXXX
            XX     X
               X XXX
            XXX  X X
                   X
            XXXXXXXX

            X

The corresponding output file would look like this:

            XXXXXX
            .. X X
            X.XX X
            ..   X
            XXXXXX

            XXXXXXXX
            XX...  X
            ...X.XXX
            XXX .X X
            .....  X
            XXXXXXXX

            X

### Test Data

First:

    XXXXXXXXX
      X     X
    X   X   X
    XXXXXX XX
    XX   X  X
      X     X
    X   X   X
    XXXXXXXXX

    XXXXXXXXXX
    X        X
      XX XXXXX
    XX       X
      XXXXXX X
    X        X
    XXXXXXXXXX

    X

Expected output:

    XXXXXXXXX
    ..X.... X
    X...X . X
    XXXXXX.XX
    XX   X. X
    ..X.... X
    X...X   X
    XXXXXXXXX

    XXXXXXXXXX
    X....    X
    ..XX.XXXXX
    XX  .....X
    ..XXXXXX.X
    X........X
    XXXXXXXXXX

    X

### Discussion

Around 10:00 a.m. on Friday morning, time was running out and my quest for a fourth interesting problem was becoming desparate. A maze problem was a quick way out -- easy to write and safe because familiar.

The maze can be solved by breadth first search (like Problem 1) but it is easier to write a backtracking function. The difficulty with backtracking is that it does not directly give you the shortest path or even -- in its basic form -- any path at all. My first solution was a backtracking progam that simply said "done it". The next step was to add the arrays `pr` and `pc` (which should be `structs` but I was hurrying) to record the path. The final step was to add the arrays `sr` and `sc` and to copy the path into them whenever a new and shorter path was found.

A backtracking algorithm must record where it has been in order to avoid looping. I did this by replacing ' ' by '*' during the traversal; then turning '*' back to ' ' to restore the original maze; and finally writing '.' in each cell on the shortest path. Crude, but it works.

### Code

    #include <iostream.h>
    #include <fstream.h>
    #include <strstrea.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>

    ifstream in;
    ofstream out;

    char m[100][100];

    int pr[100];
    int pc[100];

    int sr[100];
    int sc[100];

    int shortest = 1000;

    void step(int r, int c, int gr, int gc, int n)
    {
       m[r][c] = '*';
       pr[n] = r;
       pc[n] = c;
       if (r == gr && c == gc)
       {
          if (n < shortest)
          {
             for (int i = 0; i <= n; i++)
             {
                sr[i] = pr[i];
                sc[i] = pc[i];
                shortest = n + 1;
             }
          }
          return;
       }
       if (m[r][c+1] == ' ') step(r, c+1, gr, gc, n+1);
       if (m[r+1][c] == ' ') step(r+1, c, gr, gc, n+1);
       if (c > 0 && m[r][c-1] == ' ') step(r, c-1, gr, gc, n+1);
       if (m[r-1][c] == ' ') step(r-1, c, gr, gc, n+1);
    }

    bool getmaze()
    {
       int rows = 0;
       while (true)
       {
          in.getline(m[rows], 100);
          if (strlen(m[rows]) < 2)
             break;
          rows++;
       }
       if (rows < 2)
          return false;

       int r;
       int ent = 0;
       int ext = 0;
       for (r = 0; r < rows; r++)
       {
          if (m[r][0] == ' ')
             if (ent == 0)
                ent = r;
             else
                ext = r;
       }

       step(ent, 0, ext, 0, 0);

       for (r = 0; r < rows; r++)
          for (char *p = m[r]; *p; p++)
             if (*p == '*') *p = ' ';
       for (int i = 0; i < shortest; i++)
          m[sr[i]][sc[i]] = '.';
       for (r = 0; r < rows; r++)
          out << m[r] << endl;
       out << endl;
       return true;
    }

    void main(int argc, char *argv[])
    {
       in.open(argv[1]);
       out.open(argv[2]);
       while(getmaze());
       out << endl << 'X' << endl;
    }