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

// 坐标
typedef struct
{
    int x, y;
}SPostion;

// 栈中数据
typedef struct 
{
    SPostion mPos;  //当前坐标
    int      mDir;  //往下一坐标的方向
}SElemType;

// 链表节点
typedef struct _SNode {
    SElemType       mData;
    struct _SNode*  mNext;
} SNode;

// 链表头
struct Stack
{
    SNode *mHdr;
};

typedef struct Stack* StackRef;


//----------迷宫搜索-----------------
//初始化栈
void stack_ctor(StackRef s)
{
    s->mHdr = NULL;
}

//初始化栈
void stack_dtor(StackRef s)
{
    SNode *t, *n = s->mHdr;
    while (n){
        t = n->mNext;
        free(n);
        n = t;
    }
    s->mHdr = NULL;
}

//入栈
bool stack_push(StackRef s, SElemType e) {
    SNode *p = (SNode*)malloc(sizeof(SNode));
    if (!p) return false;
    p->mData = e;
    p->mNext = s->mHdr;
    s->mHdr = p;
    return true;
}

//出栈
bool stack_pop(StackRef s, SElemType *e)
{
    SNode *p = s->mHdr;
    if (p != NULL) {
        s->mHdr = p->mNext;
        *e = p->mData;
        free(p);
        return true;
    }
    return false;
}

//判空
bool stack_isempty(StackRef s)
{
    return (!s || s->mHdr == NULL);
}

//获取栈元素个数
int stack_length(StackRef s)
{
    SNode *p = s->mHdr;
    int i = 0;
    while (p != NULL) {
        i++;
        p = p->mNext;
    }
    return i;
}

//----------迷宫搜索-----------------
#define M 9
#define N 8
typedef enum{ eRight, eDown, eLeft, eUp } EDir;
unsigned char Mask[M + 2][N + 2];
unsigned char Maze[M + 2][N + 2]=
{
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
    { 1, 0, 1, 1, 1, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 0, 0, 0, 1, 0, 1, 1 },
    { 1, 0, 1, 1, 1, 1, 0, 0, 1, 1 },
    { 1, 1, 1, 0, 0, 0, 1, 0, 1, 1 },
    { 1, 1, 1, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};

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

void initMaze()
{
    for (int j = 1; j < M + 1; j++){
        Maze[j][0] = 1;
        Maze[j][N + 1] = 1;
    }

    for (int i = 0; i < N + 2; i++){
        Maze[0][i] = 1;
        Maze[M + 1][i] = 1;
    }

    for (int i = 1; i < M + 1; i++){
        for (int j = 1; j < N + 1; j++)
            scanf("%d", &Maze[i][j]);
    }
}

void initMask()
{
    for (int i = 0; i< M + 2; i++)
        for (int j = 0; j<N + 2; j++)
            Mask[i][j] = 0;
}

bool findThePath(StackRef stack, SPostion start, SPostion end)
{
    Mask[start.y][start.x] = 1;
    SElemType node = { start, eRight };
    stack_push(stack, node);

    while (!stack_isempty(stack)){
        stack_pop(stack, &node);

        for (int i = 0; i < sizeof(dirTbl) / sizeof(dirTbl[0]); i++){
            int x = node.mPos.x + dirTbl[i].x;
            int y = node.mPos.y + dirTbl[i].y;
            if (Maze[y][x] == 0 && Mask[y][x] == 0){
                node.mDir = (EDir)i;
                stack_push(stack, node);

                Mask[y][x] = 1;
                node.mPos.x = x;
                node.mPos.y = y;
                node.mDir = eRight;
                stack_push(stack, node);
                if (y == end.y && x == end.x)
                    return true;
                break;
            }
        }
    }
    return false;
}

//----------迷宫绘制-----------------
#define MEX (M+2)
#define NEX (N+2)
char showMaze[MEX][NEX * 2 + 1] = {};
void initShowMaze()
{
    const char* kong = "  ";
    const char* qiang = "■";
    for (int i = 0; i < MEX; i++){
        for (int j = 0; j < NEX; j++){
            if (Maze[i][j] == 1){
                showMaze[i][j * 2] = qiang[0];
                showMaze[i][j * 2 + 1] = qiang[1];
            }
            else{
                showMaze[i][j * 2] = kong[0];
                showMaze[i][j * 2 + 1] = kong[1];
            }
        }
    }
}

int main()
{
    Stack st;
    stack_ctor(&st);
    //initMaze();
    initMask();
    initShowMaze();
    if (findThePath(&st, {1, 1}, {8, 9})){
        int count = 0;
        SElemType tbl[500];
        while (!stack_isempty(&st)){
            stack_pop(&st, &tbl[count++]);
        }

        while (count-- > 0){
            int x = tbl[count].mPos.x;
            int y = tbl[count].mPos.y;
            printf("(%d,%d,%d),", x, y, tbl[count].mDir + 1);

            /*绘制路径*/
            //--x; --y;
            const char* lujin = "☆";
            showMaze[y][x * 2] = lujin[0];
            showMaze[y][x * 2 + 1] = lujin[1];
        }
    }
    else
        printf("No Path\n");

    for (int i = 0; i < MEX; ++i) {
        printf("%s\n", showMaze[i]);
    }
    stack_dtor(&st);
    return 0;
}