#include <stdio.h>
#define SX 10
#define SY 10

struct point
{
    short x;
    short y;
};
int search(const char m[SX][SX + 1], point path[], int count, const point& endPt);
void main()
{
    char maze[SY][SX + 1]=
    {
        "XXXXXXXXXX",
        "X       XX",
        "X XX XXXXX",
        "   X XXXXX",
        "XXXX XXXXX",
        "X       XX",
        "X XXXXX XX",
        "X XXXXX XX",
        "X   XXX   ",
        "XXXXXXXXXX",
    };

    point endPt;
    point path[128];

    /*起点*/
    path[0].x = 0;
    path[0].y = 3;
    /*终点*/
    endPt.x = 9; endPt.y = 8;

    /*路线长度*/
    int count = search(maze, path, 0, endPt);
    if (0 == count) {
        printf("bad path\n");
        return;
    }

    /*绘制路径*/
    for (int i = count; i--;) {
        maze[path[i].y][path[i].x] = '.';
    }
    for (int i = 0; i < SY; ++i) {
        printf("%s\n", maze[i]);
    }

    printf("迷宫自动寻路完成\n");
}

point dirTbl[] =
{
    { -1,0 },
    { 1,0 },
    { 0,-1 },
    { 0,1 },
};

int search(const char maze[SY][SX + 1], point path[], int count, const point& endPt)
{
    if (path[count].x == endPt.x && path[count].y == endPt.y)
        return count + 1;

    int ret = 0;
    int index = count + 1;
    for (short i = 0; i < sizeof(dirTbl)/sizeof(dirTbl[0]); ++i) {
        /*下一个点*/
        short x = path[count].x + dirTbl[i].x;
        short y = path[count].y + dirTbl[i].y;
        /*边界检查*/
        if (x < 0 || y < 0) continue;
        if (x >= SX || y >= SY) continue;
        /*防止回头路*/
        if (count && x == path[count-1].x && y == path[count-1].y)
            continue;
        if (maze[y][x] != ' ') continue;

        path[index].x = x;
        path[index].y = y;
        ret = search(maze, path, index, endPt);
        if(ret == 0) continue;
        return ret;
    }
    return 0;
}