解迷宮

maze.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

void loadmap(char *, int **, int *, int *, int *, int *);
void gomap(int *, int *, int *, int, int, int);
void backmap(int *, int *, int *, int *, int, int);
int summap(int *, int);

int main(int argc, char *argv[])
{
    int *map, *cmap, *wmap;
    int mapsize, size_x, size_y, start, goal;
    int i, j;
    int steps, ways;

    if(argc != 2)
    {
        printf("No input file selected.\n");
        return 0;
    }

    loadmap(argv[1], &map, &size_x, &size_y, &start, &goal);

    mapsize = size_x * size_y;
    printf("Map Width:  %d\nMap Height: %d\n", size_x, size_y);

    cmap = (int *)calloc(mapsize, sizeof(int));

    gomap(map, cmap, &map[start], size_x, size_y, 1);
    steps = cmap[goal];

    if(steps)
    {
        printf("To cross the map needs at least %d step(s).\n", steps);

        wmap = (int *)calloc(mapsize, sizeof(int));

        backmap(map, cmap, wmap, &map[goal], size_x, size_y);
        ways = summap(wmap, mapsize);

        printf("There are %d shortest way(s) to cross the map.\n", ways);
    }
    else
    {
        printf("There are no way to cross the map.\n");
    }
    return 0;
}

void loadmap(char *mapfile, int **map_rtn, int *size_x, int *size_y, int *start, int *goal)
{
    int *map = (int *)malloc(sizeof(int) * 1);
    int lines, len, c, width, height;
    int i, j, sx, sy, gx, gy;
    char *tmp = (char *)malloc(sizeof(char) * 16);
    FILE *fp;

    c = 0;
    width = 0;
    height = 0;

    fp = fopen(mapfile, "r");
    if(fgets(tmp, 16, fp))
    {
        sscanf(tmp, "%d%d%d%d", &sx, &sy, &gx, &gy);
    }
    while(fgets(tmp, 16, fp))
    {
        len = strlen(tmp);
        if(tmp[len - 1] == '\n')
        {
            --len;
            if(!width)
            {
                width = c + len;
            }
            ++height;
        }
        c += len;
        map = (int *)realloc(map, sizeof(int) * c);
        for(i = 0; i < len; ++i)
        {
            j = c - len + i;
            map[j] = tmp[i] - 48;
        }
    }
    fclose(fp);

    *start = sx + sy * width;
    *goal = gx + gy * width;

    *map_rtn = map;
    *size_x = width;
    *size_y = height;
}

void gomap(int *map, int *cmap, int *p, int size_x, int size_y, int i)
{
    int mapsize = size_x * size_y;

    cmap[p - map] = i;

    if(p - size_x >= map && map[p - size_x - map])
    {
        if(cmap[p - size_x - map] > i + 1 || !cmap[p - size_x - map])
        {
            gomap(map, cmap, p - size_x, size_x, size_y, i + 1);
        }
    }

    if(p - 1 >= map && map[p - 1 - map])
    {
        if(cmap[p - 1 - map] > i + 1 || !cmap[p - 1 - map])
        {
            gomap(map, cmap, p - 1, size_x, size_y, i + 1);
        }
    }

    if(p + size_x < map + mapsize && map[p + size_x - map])
    {
        if(cmap[p + size_x - map] > i + 1 || !cmap[p + size_x - map])
        {
            gomap(map, cmap, p + size_x, size_x, size_y, i + 1);
        }
    }

    if(p + 1 < map + mapsize && map[p + 1 - map])
    {
        if(cmap[p + 1 - map] > i + 1 || !cmap[p + 1 - map])
        {
            gomap(map, cmap, p + 1, size_x, size_y, i + 1);
        }
    }
}

void backmap(int *map, int *cmap, int *wmap, int *p, int size_x, int size_y)
{
    int mapsize = size_x * size_y;
    int x_up, x_dn, x_lf, x_rt;

    x_up = p - size_x >= map && map[p - size_x - map] && cmap[p - size_x - map] == cmap[p - map] - 1;
    x_dn = p + size_x < map + mapsize && map[p + size_x - map] && cmap[p + size_x - map] == cmap[p - map] - 1;
    x_lf = p - 1 >= map && map[p - 1 - map] && cmap[p - 1 - map] == cmap[p - map] - 1;
    x_rt = p + 1 < map + mapsize && map[p + 1 - map] && cmap[p + 1 - map] == cmap[p - map] - 1;

    if(!wmap[p - map])
    {
        wmap[p - map] = (x_up? 1: 0) + (x_dn? 1: 0) + (x_lf? 1: 0) + (x_rt? 1: 0);

        if(x_up) backmap(map, cmap, wmap, p - size_x, size_x, size_y);
        if(x_dn) backmap(map, cmap, wmap, p + size_x, size_x, size_y);
        if(x_lf) backmap(map, cmap, wmap, p - 1, size_x, size_y);
        if(x_rt) backmap(map, cmap, wmap, p + 1, size_x, size_y);
    }
}

int summap(int *map, int mapsize)
{
    int i, sum = 0;

    for(i = 0; i < mapsize; ++i)
    {
        if(map[i] > 1)
        {
            sum += map[i] - 1;
        }
    }

    return sum + 1;
}