maze.c

#include <stdio.h>

#define N (12)

struct vec {
    int x, y;
};

struct state {
    struct vec p;
    int d;
    int t;
    int bt;
};

int main() {
    char M[N][N];
    for (int x=0; x<N; x++) {
        for (int y=0; y<N; y++) {
            M[x][y] = '+';
        }
    }

    for (int x=1; x<11; x++) {
        char line[12];
        scanf("%s\n", line);
        for (int y=0; y<10; y++) {
            M[x][y+1] = line[y];
        }
    }

    struct vec S;
    for (int x=0; x<N; x++) {
        for (int y=0; y<N; y++) {
            char c = M[x][y];
            if (c == 'S') {
                S.x = x;
                S.y = y;
            }
        }
    }

    int T[N][N][4];
    for (int x=0; x<N; x++) {
        for (int y=0; y<N; y++) {
            for (int d=0; d<4; d++) {
                T[x][y][d] = 1<<30;
            }
        }
    }

    struct state B[N*N*4];
    int b = 0, a = 0;

    for (int d=0; d<4; d++) {
        B[b].p = S;
        B[b].d = d;
        B[b].t = 0;
        B[b].bt = -1;
        b++;
    }

    while (a < b) {
        struct state s = B[a];
        s.bt = a++;
        // printf("(%d, %d) %d %d\n", s.p.x, s.p.y, s.d, s.t);
        if (T[s.p.x][s.p.y][s.d] <= s.t) {
            continue;
        }
        T[s.p.x][s.p.y][s.d] = s.t;
        s.t++;

        if (M[s.p.x][s.p.y] == 'E') {
            struct state bt = B[s.bt];
            do {
                M[bt.p.x][bt.p.y] = 'o';
                bt = B[bt.bt];
            } while (bt.bt != -1);
            M[s.p.x][s.p.y] = 'E';
            for (int x=0; x<N; x++) {
                for (int y=0; y<N; y++) {
                    printf("%c", M[x][y]);
                }
                printf("\n");
            }
            return 0;
        }

        struct vec v;
        v.x =  (s.d&1) ? ((s.d&2) ? 1 : -1) : 0;
        v.y = !(s.d&1) ? ((s.d&2) ? 1 : -1) : 0;

        s.p.x += v.x;
        s.p.y += v.y;
        char c = M[s.p.x][s.p.y];
        if (c == '+') {
            s.p.x -= v.x;
            s.p.y -= v.y;
            for (int d=0; d<4; d++) {
                B[b] = s;
                B[b].d = d;
                // printf("  ->  (%d, %d) %d %d\n", s.p.x, s.p.y, B[b].d, s.t);
                b++;
            }
        }

        else {
            B[b] = s;
            b++;
        }
    }

    printf("maze is impossible!\n");
    return 0;
}

sample.in

S......+++
++++++.+++
++++++.+++
++++++.+++
++++++.+++
++++++.+++
+++.++.+++
+++.++.+++
+++.++.+++
+++......E