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
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
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.
#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;
}