#include <stdio.h>
#include <windows.h>
#include <string>

//設定全域數值
#define FILE_MAP "input_map.txt"
#define FILE_OUTPUT "output_route.txt"      //人機輸出
#define MAP_MAXSIZE_X 100
#define MAP_MAXSIZE_Y 100
#define MAX_STACK (MAP_MAXSIZE_X*MAP_MAXSIZE_Y)/2
#define bool int
#define true 1
#define false 0                            //設定參數

int max_x=0, max_y=0;
char map[MAP_MAXSIZE_X][MAP_MAXSIZE_Y]={1};
bool passed[MAP_MAXSIZE_X][MAP_MAXSIZE_Y]={0};    //設定初始值

struct _POSITION           // 設定座標結構
{
    int x;
    int y;
};

typedef struct _POSITION POSITION;
POSITION stack[MAX_STACK];         //堆疊數據
int top = -1;                      //最頂堆疊數據

//如果堆疊是空的
bool Empty()
{
    if(top == -1)
        return true;
    return false;
}

// 如果堆疊是滿的
bool Full()
{
    if(top < MAX_STACK-1)
        return false;
    return true;
}

// 從堆疊跳出
POSITION Pop()
{
    return stack[top--];
}

// 把數據寫入堆疊
void Push(POSITION posData)
{
    stack[++top]=posData;
}

void run(int x, int y)
{
    FILE *fptr;
    POSITION last; //最後坐標資訊
    unsigned int branch = 0; //分支碼
    int direction = 1; // 1:東  2:南  3:西  4:北

    fptr = fopen(FILE_OUTPUT, "w");

    while(map[x][y] != 'O') //達到目標前持續做
    {
        branch = 0;         // 分支數據清零
        passed[x][y] = 1;   // 設定此位置可通過

        // 指令：選一條路走
        if((y+1<max_y) && ((map[x][y+1] == 'O') || (map[x][y+1] == '0'))  // 假如東方可以過(尚未過去)
            && (passed[x][y+1] == 0))
        {
            branch++;         // 增加分支(假如這可以過)
            direction = 1;
        }
        if((x+1<max_x) && ((map[x+1][y] == 'O') || (map[x+1][y] == '0'))  // 假如西方可以過(尚未過去)
            && (passed[x+1][y] == 0))
        {
            branch++;         // 增加分支(假如這可以過)
            direction = 2;
        }
        if((y-1>=0) && ((map[x][y-1] == 'O') || (map[x][y-1] == '0'))     // 假如南方可以過(尚未過去)
            && (passed[x][y-1] == 0))
        {
            branch++;         // 增加分支(假如這可以過)
            direction = 3;
        }
        if((x-1>=0) && ((map[x-1][y] == 'O') || (map[x-1][y] == '0'))     // 假如北方可以過(尚未過去)
            && (passed[x-1][y] == 0))
        {
            branch++;         // 增加分支(假如這可以過)
            direction = 4;
        }

        // 指令：前進
        if(branch > 1)       //假如分支不只一個
        {
            if(!Full())      // 假如堆疊不是滿的(把分支寫入堆疊)
            {
                last.x = x;
                last.y = y;
                Push(last);
                printf("Push(%d,%d), ", last.x+1, last.y+1);
                fprintf(fptr, "Push(%d,%d), ", last.x+1, last.y+1);
            }
        }
        else if(branch == 0) // 假如不能通過
        {
            printf("遇到死路, ");
            fprintf(fptr, "遇到死路, ");
            if(!Empty())
            {
                last = Pop();
                x = last.x;
                y = last.y;
                printf("(%d,%d) = Pop(), ", last.x+1, last.y+1);
                fprintf(fptr, "(%d,%d) = Pop(), ", last.x+1, last.y+1);
            }
            else
            {
                printf("無法離開\n");
                fprintf(fptr, "無法離開\n");
                fclose(fptr);
                return;
            }
            continue;
        }

        //指令：在最後的方向選擇一種方式前進
        switch(direction)     //fptr:輸出檔案用
        {                     //printf:人機
            case 1:
                y = y + 1;
                printf("右, ");
                fprintf(fptr, "右, ");
                break;
            case 2:
                x = x + 1;
                printf("下, ");
                fprintf(fptr, "下, ");
                break;
            case 3:
                y = y - 1;
                printf("左, ");
                fprintf(fptr, "左, ");
                break;
            case 4:
                x = x - 1;
                printf("上, ");
                fprintf(fptr, "上, ");
                break;
        }
    }

    printf("到達\n");
    fprintf(fptr, "到達\n");

    fclose(fptr);
}

int main()
{
    FILE *fptr;
    int i,j,start_x,start_y;

    // 指令：加載文件
    fptr = fopen(FILE_MAP,"w");
    if(!fptr)
    {
        printf("File loaded error!\n");
        return 0;
    }

    // 指令：讀取文件
    fscanf(fptr, "%d %d\n",&max_x, &max_y);
    if(max_x==0 || max_y==0)
        return 0;
    for(i=0;i<max_x;i++)
    {
        for(j=0;j<max_y;j++)
        {
           fscanf(fptr, " %c", &map[i][j]);
           passed[i][j]=0;
           if(map[i][j]=='M')
           {
               start_y=i;
               start_x=j;
           }
        }
    }
    fclose(fptr);

    // 指令：匯出迷宮圖
    for(i=0;i<max_x;i++)
    {
        for(j=0;j<max_y;j++)
        {
           printf("%c ", map[i][j]);
        }
        printf("\n");
    }

    run(start_y,start_x); // 跑迷宮

    system("pause");
    return 0;
}