/* ======================================================================== */ /* CONTEST 9: Maze Solver (ORIGINAL version) */ /* Joseph Zbiciak, im14u2c@primenet.com. */ /* ======================================================================== */ /* ======================================================================== */ /* This program is free software; you can redistribute it and/or modify */ /* it under the terms of the GNU General Public License as published by */ /* the Free Software Foundation; either version 2 of the License, or */ /* (at your option) any later version. */ /* */ /* This program is distributed in the hope that it will be useful, */ /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */ /* General Public License for more details. */ /* */ /* You should have received a copy of the GNU General Public License */ /* along with this program; if not, write to the Free Software */ /* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* ======================================================================== */ /* Copyright (c) 2000, Joseph Zbiciak */ /* ======================================================================== */ #include #include #include /* ======================================================================== */ /* Define the maximum permitted maze dimensions. */ /* ======================================================================== */ #define MAX_X (256) #define MAX_Y (512) #define MAX_I ((MAX_X * MAX_Y + 3) / 4) char maze[MAX_Y][MAX_X]; /* ======================================================================== */ /* Shortcut arrays which describe "delta-X" and "delta-Y" for the four */ /* directions we may travel. This replaces conditional code (eg. if/else) */ /* with a simple table lookup. Lookups tend to be faster than branches. */ /* ======================================================================== */ /* D L R U */ const int dx[4] = { 0, -1, 1, 0 }; const int dy[4] = { 1, 0, 0, -1 }; #ifndef NDEBUG void dump_maze(void); #endif /* ======================================================================== */ /* We keep our list of active maze traversal points in a circular buffer */ /* of X/Y coordinates. The buffer forms a queue. */ /* ======================================================================== */ #define MAX_S (32768) #define SMASK (MAX_S - 1) int xpos[MAX_S]; int ypos[MAX_S]; int head = 0; int tail = 0; /* ======================================================================== */ /* SOLVE -- Perform a breadth-first traversal of the maze. */ /* ======================================================================== */ int solve(int sx, int sy) { int x, y, idx, nx, ny, i; /* -------------------------------------------------------------------- */ /* Seed our work-queue with a single node to the right of the 's' at */ /* the start. Our work-queue represents a "constant path-length */ /* contour" in the maze, and as soon as we touch 'f', we know we've */ /* found the shortest path from 's' to 'f'. */ /* -------------------------------------------------------------------- */ xpos[0] = sx + 1; ypos[0] = sy; head = 1; tail = 0; maze[sy][sx + 1] = 'S'; /* -------------------------------------------------------------------- */ /* While there are still active nodes in our work-queue, advance the */ /* contour. We advance down, left, right, and up in that order to */ /* meet the "alphabetical order" criteria in the contest rules. */ /* -------------------------------------------------------------------- */ while (tail < head) { /* ---------------------------------------------------------------- */ /* Extract the x/y coordinates from the top of the queue. */ /* ---------------------------------------------------------------- */ idx = tail++ & SMASK; x = xpos[idx]; y = ypos[idx]; /* ---------------------------------------------------------------- */ /* Attempt to move Down/Left/Right/Up from that point, putting */ /* new positions at the end of the queue for successful moves. */ /* We move in D/L/R/U order to meet the alphabetical-ordering */ /* requirements for parallel paths. Stop when we see the 'f'. */ /* ---------------------------------------------------------------- */ for (i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (maze[ny][nx] == ' ') { xpos[head & SMASK] = nx; ypos[head & SMASK] = ny; head++; maze[ny][nx] = i; } if (maze[ny][nx] == 'f') { maze[ny][nx] = i; return 0; } } } /* -------------------------------------------------------------------- */ /* If we get here, the maze has no solution, so return failure. */ /* -------------------------------------------------------------------- */ return -1; } char soln[MAX_S + 2]; /* ======================================================================== */ /* RETRACE -- Retrace our solution from the 'f' back to the 's' so that */ /* we can report it. */ /* ======================================================================== */ char * retrace(int x, int y) { int m; char *s; /* -------------------------------------------------------------------- */ /* Start filling our solution string at the end and work backwards. */ /* -------------------------------------------------------------------- */ s = &soln[MAX_S + 1]; *s = '\0'; *--s = '\n'; /* -------------------------------------------------------------------- */ /* Trace from the 'f' until we find our starting position (marked by */ /* a capital 'S' by the the solver above). */ /* -------------------------------------------------------------------- */ while ((m = maze[y][x]) != 'S') { *--s = "DLRU"[m]; x -= dx[m]; y -= dy[m]; } *--s = 'R'; /* -------------------------------------------------------------------- */ /* Return the solution string. */ /* -------------------------------------------------------------------- */ return s; } /* ======================================================================== */ /* READ_MAZE -- Reads the next maze from a file, and sets up sx/sy/fx/fy */ /* ======================================================================== */ char buf[MAX_X + 8]; int sx, sy, fx, fy, my; int read_maze(FILE *f) { int y; char *s; /* -------------------------------------------------------------------- */ /* Process lines from the file until we reach EOF or see a line that */ /* starts with a '/' character. */ /* -------------------------------------------------------------------- */ y = 0; while (fgets(buf, MAX_X + 8, f) != NULL) { /* ---------------------------------------------------------------- */ /* If we see a '/', exit. If we see a 's', remember it. */ /* ---------------------------------------------------------------- */ if (buf[0] == '/') { my = y; return 0; } if (buf[0] == 's') { sx = 0; sy = y; } /* ---------------------------------------------------------------- */ /* Look for the last space on the line. This delimits the right */ /* edge of the maze. If there's an 'f' to the right of it, then */ /* remember the 'f' and adjust our position. */ /* ---------------------------------------------------------------- */ s = strrchr(buf, ' '); if (s[1] == 'f') { fx = ++s - buf; fy = y; } /* ---------------------------------------------------------------- */ /* Copy the line to our maze buffer. */ /* ---------------------------------------------------------------- */ memcpy(&maze[y][0], buf, s + 1 - buf); y++; } my = y; /* -------------------------------------------------------------------- */ /* Return whether we found a maze or not. */ /* -------------------------------------------------------------------- */ return y > 0 ? 0 : -1; } /* ======================================================================== */ /* DUMP_MAZE -- Debugging code that was disabled in the contest build. */ /* ======================================================================== */ #ifndef NDEBUG void dump_maze(void) { int xx, yy; for (yy = 0; yy < my; yy++) { for (xx = sx; xx <= fx; xx++) { int m = maze[yy][xx]; if (m < ' ') m = "DLRU"[m]; putchar(m); } putchar('\n'); } } #endif /* ======================================================================== */ /* MAIN -- Where the action happens. */ /* ======================================================================== */ main() { FILE *fi, *fo, *fs; int end_time, maze_num = 0; /* -------------------------------------------------------------------- */ /* Open our input files and see how much time we have. */ /* -------------------------------------------------------------------- */ fi = fopen("input2.txt", "r"); fo = fopen("output.txt", "w"); fs = fopen("seconds.txt", "r"); if (fs) { fscanf(fs, "%d", &end_time); } else { end_time = 30; } end_time += time(0); /* -------------------------------------------------------------------- */ /* While we still have time left and we still have mazes, solve 'em. */ /* -------------------------------------------------------------------- */ while (time(0) < end_time && read_maze(fi) >= 0) { maze_num++; printf("\r%d", maze_num); if (solve(sx, sy) < 0) fprintf(fo, "no answer\n"); else fputs(retrace(fx, fy), fo); } /* -------------------------------------------------------------------- */ /* Tell the user how many we solved in the time alotted. */ /* -------------------------------------------------------------------- */ printf("\r%d\n", maze_num); fclose(fi); fclose(fo); return 0; }