[HaBo]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define UPPER 1
#define RIGHT 2
#define LOWER 4
#define LEFT  8

#define START   16
#define END     32
#define VISITED 64

typedef struct {
    int xdim, ydim;   /* size */
    char **lab;
} labyrinth;

void *xmalloc(int size);    /* malloc() with automatic errorchecking */
labyrinth *getLab(int xdim, int ydim);
void createWays(labyrinth *l, int x, int y);
int solveRecur(labyrinth *l, int x, int y);
void solve(labyrinth *l);
void printLab(labyrinth *l);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "usage: %s <x-dimension> <y-dimension>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    int x, y;
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    labyrinth *l = getLab(x, y);

    srand( time(NULL) );
    createWays(l, rand() % l->xdim, rand() % l->ydim);
    solve(l);

    printLab(l);

    return EXIT_SUCCESS;
}

void solve(labyrinth *l) {
    int endx, endy;
    int startx = rand() % l->xdim;
    int starty = rand() % l->ydim;
    l->lab[starty][startx] ^= START;
    do {
        endx = rand() % l->xdim;
        endy = rand() % l->ydim;
    } while (endx == startx && endy == starty);

    l->lab[endy][endx] ^= END;
    solveRecur(l, startx, starty);
}

int solveRecur(labyrinth *l, int x, int y) {
    l->lab[y][x] ^= VISITED;
    if (l->lab[y][x] & END) {
        return 1;
    }
    int i;
    for (i = 0; i < 4; i++) {
        if (i == 0) {
            if (
                y > 0
             && !(l->lab[y][x] & UPPER)
             && !(l->lab[y-1][x] & VISITED)
            ) {
                if (solveRecur(l, x, y-1)) {
                    return 1;
                }
            }
        }
        else if (i == 1) {
            if (
                y < (l->ydim - 1)
             && !(l->lab[y][x] & LOWER)
             && !(l->lab[y+1][x] & VISITED)
            ) {
                if (solveRecur(l, x, y+1)) {
                    return 1;
                }
            }
        }
        else if (i == 2) {
            if (
                x > 0
             && !(l->lab[y][x] & LEFT)
             && !(l->lab[y][x-1] & VISITED)
            ) {
                if (solveRecur(l, x-1, y)) {
                    return 1;
                }
            }
        }
        else if (i == 3) {
            if (
                x < (l->xdim - 1)
             && !(l->lab[y][x] & RIGHT)
             && !(l->lab[y][x+1] & VISITED)
            ) {
                if (solveRecur(l, x+1, y)) {
                    return 1;
                }
            }
        }
    }
    l->lab[y][x] ^= VISITED;
    return 0;
}

void createWays(labyrinth *l, int x, int y) {
    int choice, gone = 0;
    while (gone != 15) {
        do {
            choice = rand() % 4;
            choice = 1 << choice;
        } while (choice & gone);

        if (choice == UPPER) {
            if (y > 0 && l->lab[y-1][x] == 15) {
                l->lab[y][x] &= ~ UPPER;
                l->lab[y-1][x] &= ~ LOWER;
                createWays(l, x, y-1);
            }
            gone |= UPPER;
        }
        else if (choice == LOWER) {
            if (y < (l->ydim-1) && l->lab[y+1][x] == 15) {
                l->lab[y][x] &= ~ LOWER;
                l->lab[y+1][x] &= ~ UPPER;
                createWays(l, x, y+1);
            }
            gone |= LOWER;
        }
        else if (choice == LEFT) {
            if (x > 0 && l->lab[y][x-1] == 15) {
                l->lab[y][x] &= ~ LEFT;
                l->lab[y][x-1] &= ~ RIGHT;
                createWays(l, x-1, y);
            }
            gone |= LEFT;
        }
        else if (choice == RIGHT) {
            if (x < (l->xdim-1) && l->lab[y][x+1] == 15) {
                l->lab[y][x] &= ~ RIGHT;
                l->lab[y][x+1] &= ~ LEFT;
                createWays(l, x+1, y);
            }
            gone |= RIGHT;
        }
    }
}

labyrinth *getLab(int xdim, int ydim) {
    char *rows = xmalloc(xdim * ydim);
    char **cols = xmalloc(ydim * sizeof(char *));
    int i, j;
    for (i = 0; i < ydim; i++) {
        cols[i] = &rows[i * xdim];
        for (j = 0; j < xdim; j++) {
            cols[i][j] = 15; /* all walls are up */
        }
    }
    labyrinth *l = xmalloc(sizeof(labyrinth));
    l->lab = cols;
    l->xdim = xdim;
    l->ydim = ydim;
    return l;
}

void printLab(labyrinth *l) {
    int x, y, floor;
    char *e, *e2, *f = "##";
    printf("\n\n");
    for (x = 0; x < l->xdim; x++) {
        printf("%s%s", f, f);
    }
    printf("##\n");
    for (y = 0; y < l->ydim; y++) {
        for (floor = 0; floor < 2; floor++) {
            for (x = 0; x < l->xdim; x++) {
                e =   (l->lab[y][x] & START)
                    ? ":o"
                    : (l->lab[y][x] & END)
                    ? ":D"
                    : (l->lab[y][x] & VISITED)
                    ? ".."
                    : "  ";
                e2 = e;
                if (floor == 0) {
                    if (x > 0 && !(l->lab[y][x-1] & VISITED)) {
                        e2 = "  ";
                    }
                    printf("%s%s", l->lab[y][x] & LEFT ? f : e2, e);
                }
                else if (floor == 1) {
                    if (y < (l->ydim - 1) && !(l->lab[y+1][x] & VISITED)) {
                        e2 = "  ";
                    }
                    printf("%s%s", f, l->lab[y][x] & LOWER ? f : e2);
                }
            }
            printf("##\n");
        }
    }

}

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}