Code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "sp.h"
MAP map;
int dist[MAX_R][MAX_C];
int parent[MAX_R][MAX_C][2];
int startr, startc;
int endr, endc;
int rows_read, cols_read;
int pops;
int debug_level = 0;
extern int max_memory;
int
map_read(char * fname)
{
FILE * file;
int row, col;
char line[MAX_C*2+1], * line_ptr;
if ((file = fopen(fname, "r")) == NULL) return(-1);
cols_read = 0;
for (row = 0; row < MAX_R && ! feof(file); row++) {
if (fgets(line, MAX_C*2, file) == NULL) break;
printf("%s",line);
for (col = 0, line_ptr = line; col < MAX_C && *line_ptr; col++, line_ptr++)
if (isdigit(*line_ptr))
map[row][col] = *line_ptr - '0';
else
map[row][col] = INFINITY;
if (col > cols_read) cols_read = col - 1;
for (; col < MAX_C; col++) map[row][col] = INFINITY;
}
rows_read = row;
for ( ; row < MAX_R; row++)
for (col = 0; col < MAX_C; col++)
map[row][col] = INFINITY;
fclose(file);
for (row = 0; row < MAX_R; row++)
for (col = 0; col < MAX_C; col++) {
dist[row][col] = INFINITY;
parent[row][col][0] = -1;
parent[row][col][1] = -1;
}
startr = startc = endr = endc = -1;
return(0);
}
void
map_draw_path(void)
{
int row, col;
int wt;
wt = 0;
for (row = 0; row < rows_read; row++) {
for (col = 0; col < cols_read; col++) {
if (startr == row && startc == col)
putc('^', stdout);
else if (endr == row && endc == col)
putc('$', stdout);
else if (parent[row][col][0] >= 0 && parent[row][col][1] >= 0) {
putc('+', stdout);
wt += map[row][col];
} else if (map[row][col] < INFINITY)
putc('.', stdout);
else
putc('#', stdout);
}
printf("\n");
}
printf ("\nThe weight of this path is: %d\n", wt);
}
#define drow(row,i) (row+delta[i][0])
#define dcol(col,i) (col+delta[i][1])
int delta[8][2] = { -1, -1, -1, 1, 1, -1, 1, 1, -1, 0, 0, 1, 1, 0, 0, -1 };
void
build_illustrate(void)
{
int i, j;
char line[256];
for (i = 0; i < rows_read; i++) {
for (j = 0; j < cols_read; j++)
if (dist[i][j] < INFINITY)
printf("%2d ", dist[i][j]);
else
printf(" I ");
printf("\n");
}
printf("\nHIT ENTER:"); fflush(stdout);
gets(line);
}
void
build_path(void)
{
PQUEUE * pq;
int row, col;
int i;
pq = pqueue_new();
if (startr < 0 || startr >= rows_read || startc < 0 || startc >= cols_read)
return;
dist[startr][startc] = 0;
parent[startr][startc][0] = -1;
parent[startr][startc][1] = -1;
pqueue_insert(pq, startr, startc, 0);
while (pqueue_popmin(pq, &row, &col) == 0) {
/* DEBUG INFORMATION */
pops++;
if (debug_level > 0)
printf("\nSelected (row,col)=(%d,%d). Adding:\n", row, col);
/* FOREACH square adjacent to (row,col), call it drow(row,i), dcol(col,i) */
for (i = 0; i < 8; i++) {
/* Check to make sure the square is on the map */
if (drow(row,i) < 0 || drow(row,i) >= rows_read ||
dcol(col,i) < 0 || dcol(col,i) >= cols_read)
continue;
/* Check to see if we've found a shorter path */
if (dist[row][col] + map[drow(row,i)][dcol(col,i)] <
dist[drow(row,i)][dcol(col,i)]) {
/* DEBUG INFORMATION */
if (debug_level > 0) {
printf("\t\t(%d,%d) Weight was/is: ", drow(row,i), dcol(col,i));
printf("%d/%d\n", dist[drow(row,i)][dcol(col,i)], map[drow(row,i)][dcol(col,i)] + dist[row][col]);
}
/* We have a shorter path, update the information */
dist[drow(row,i)][dcol(col,i)] = map[drow(row,i)][dcol(col,i)] + dist[row][col];
parent[drow(row,i)][dcol(col,i)][0] = row;
parent[drow(row,i)][dcol(col,i)][1] = col;
/* Push the modified square onto the priority queue */
pqueue_insert(pq, drow(row,i), dcol(col,i), dist[drow(row,i)][dcol(col,i)]);
} else if (debug_level >= 5) {
printf("\t\t(%d,%d) Weight Stays: %d (would have been %d)\n", drow(row,i), dcol(col,i), dist[drow(row,i)][dcol(col,i)], dist[row][col] + map[drow(row,i)][dcol(col,i)]);
}
}
if (debug_level >= 10) build_illustrate();
}
return;
}
void
limit_path(void)
{
int row, col;
int tmp;
if (endr < 0 || endr >= rows_read || endc < 0 || endc >= cols_read) return;
row = endr;
col = endc;
do {
dist[row][col] = -dist[row][col];
tmp = parent[row][col][0];
col = parent[row][col][1];
row = tmp;
} while(row >= 0 && col >= 0);
for (row = 0; row < rows_read; row++)
for (col = 0; col < cols_read; col++)
if (dist[row][col] < 0)
dist[row][col] = -dist[row][col];
else
parent[row][col][0] = -1;
return;
}
int
main(int argc, char ** argv)
{
char tmp_str[128];
if (argc > 3 || argc == 1) {
printf("USAGE: sp [-d<level>] [map filename]\n");
return(2);
}
if (argv[1][0] == '-' && argv[1][1] == 'd') {
debug_level = atoi(&argv[1][2]);
if (debug_level <= 0) debug_level = 1;
argv[1] = argv[2];
argc--;
}
map_read(argv[1]);
printf("Enter 4 integers: starting row, starting column, ending row, ending column\n");
if (scanf("%d %d %d %d", &startr, &startc, &endr, &endc) != 4) return(0);
gets(tmp_str);
pops = 0;
build_path();
if (debug_level < 10 && debug_level > 0) build_illustrate();
limit_path();
map_draw_path();
printf ("We required 2x %d queue operations\n", pops);
printf ("N = rows x cols = %d x %d = %d\n", rows_read, cols_read, rows_read * cols_read);
printf ("Maximum memory consummed in the priority queue = %d\n", max_memory);
return(0);
}