[C++] 老鼠迷宮 Mouse Maze

又來寫程式啦～這次要讓老鼠出迷宮。
作業規定：

• 至少一個stack
• 鍵盤輸入起始座標
• 老鼠能判斷重覆路徑、死路
• 顯示逃出的路線

這次沒有用class，我跟pointer還不熟，寫作業的時限又短（一部分是自己造成的），所以先用最簡單的方式做完。或許，有生之年會生一個改版出來。那麼，開始了！

== Headers ==

#include <cstdlib>
#include <iostream>
#include <stack> // 作業規定
#include <fstream> // 讀入txt檔
#include <ctime> // 原本是用亂數選擇起始點
using namespace std;

== Functions ==

bool isDeadEnd(int east, int west, int north, int south)
{
    return (east != 0 && west != 0 && north != 0 && south != 0);
}

↑判斷是否是死路
test if four directions are all dead ends

bool isOnlyWay(int east, int west, int north, int south)
{
    if ((east == 0 && west != 0 && north != 0 && south != 0) ||
        (east != 0 && west == 0 && north != 0 && south != 0) ||
        (east != 0 && west != 0 && north == 0 && south != 0) ||
        (east != 0 && west != 0 && north != 0 && south == 0))
    return true;
    else
    return false;
}

↑判斷是否只有一個出路（除了上一步）
test if there's only one way to go

void locateDir(int east, int west, int north, int south, int & mouseRow, int & mouseColumn)
{
    if (east == 0)
    mouseColumn += 1;
    else if (south == 0)
    mouseRow += 1;
    else if (west == 0)
    mouseColumn -= 1;
    else if (north == 0)
    mouseRow -= 1;
}

↑設定老鼠的習性：遇到岔路時優先選哪個方向？
priority of choices

== Main Function ==

int main(int argc, char *argv[])
{
    /* 原始讀檔設定中，0是通道、1是牆
     * 0 is passable
     * 1 is wall
     * 3 is point passed 我設定3是最終路徑
     * 8 is dead path 有走過並判斷是死路
     * 3 & 8 is made to notify the mouse to avoid used path
     */

    const int MAX_ROW = 10;
    const int MAX_COLUMN = 12;
    int maze[MAX_ROW][MAX_COLUMN];

↑設定const長寬，以便往後使用和修改；建立迷宮array
use const ints to set up the maze array

    ifstream inputFile;
    inputFile.open("maze.txt");
    int inputNum;
    for (int i = 0; i < MAX_ROW; i++) // set up the maze
    {
        for (int j = 0; j < MAX_COLUMN; j++)
        {
            inputFile >> inputNum;
            maze[i][j] = inputNum;
        }
    }

↑讀檔並輸入到迷宮中
read from file and put into the maze

    /* generate random start point and avoid placing mouse on the wall or at the exit
     * because of this setting, there is no other filter solving the problem which
     * mouse is at a improper spot(eg. on the wall or at the exit)
     *
     * srand(time(0));
     * int mouseRow = rand() % 8 + 1;
     * int mouseColumn = rand() % 10 + 1;
     * while (maze[mouseRow][mouseColumn] == 1)
     * {
     *     mouseRow = rand() % 8 + 1;
     *     mouseColumn = rand() % 10 + 1;
     * }
     *
     */

↑原本是用亂數取點，後來老師說用鍵盤輸入比較好，不過這個我還是留著紀念啦

    for (int i = 0; i < MAX_ROW; i++)
    {
        for (int j = 0; j < MAX_COLUMN; j++)
        {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }

↑只是把原始的迷宮秀出來
print the original maze

    int inputRow;
    int inputColumn;
    int mouseRow;
    int mouseColumn;
    bool isGoodStarting = false;

↑定義array的座標點和輸入的座標點
enter the row and column by keyboard

    while (!isGoodStarting)
    {
        cout << "Please enter the starting point: (Row, Column)" << endl;
        cin >> inputRow >> inputColumn;
        mouseRow = inputRow - 1;
        mouseColumn = inputColumn - 1;
        if (maze[mouseRow][mouseColumn] == 1)
        cout << "The mouse is on the wall. Please select another point." << endl;
        else if (mouseRow <= 0 || mouseRow >= (MAX_ROW - 1) ||
                 mouseColumn <= 0 || mouseColumn >= (MAX_COLUMN - 1))
        {
            cout << "The mouse is already at the exit or outside the maze." << endl;
            cout << "Please select another point to torture it." << endl;
        }
        else
        isGoodStarting = true;
    }

↑測試輸入的座標，如果不在通道、或是在出口，則回報錯誤並要求重新輸入
test if the mouse is put at invalid spots

    cout << "The first spot is " << mouseRow + 1 << ", " << mouseColumn + 1 << endl;

↑顯示起始座標
show the first point

    stack<int> mouseStack; // final moves
    stack<int> criticalStack; // critical points
    criticalStack.push(mouseRow * MAX_COLUMN + mouseColumn);

↑建立兩個stack...我本來有個規劃是六個stack XD
第一個mouseStack是儲存預計最後要輸出的路徑；
第二個criticalStack記錄岔路。
至於怎麼把X軸Y軸放進一個整數(int)的stack？把它換算成一個獨一無二的整數就好了。這招是教授提示的。
最後，先把起始點推進第二個stack。

    while (mouseRow > 0 && mouseRow < (MAX_ROW - 1) && mouseColumn > 0 && mouseColumn < (MAX_COLUMN - 1))
    {
        // set variables of directions
        int east = maze[mouseRow][mouseColumn + 1];
        int west = maze[mouseRow][mouseColumn - 1];
        int north = maze[mouseRow - 1][mouseColumn];
        int south = maze[mouseRow + 1][mouseColumn];

↑啊，這次都是用while loop...
while loop是設定當老鼠走到邊界時就跳出。因為老鼠不能撞牆，所以到邊界等於到出口了。
然後設四個方向座標的變數。

== First Condition ==

進入迴圈後，老鼠要判斷三種情況：死路、唯一選擇、或多重選擇。
我不知道這樣邏輯有沒有完美（可見沒有啊不然怎麼會不知道），不過至少很合用。
第一項是「死路」。

        if (isDeadEnd(east, west, north, south))
        {
            maze[mouseRow][mouseColumn] = 8;
            // load back to the last critical point
            mouseRow = criticalStack.top() / MAX_COLUMN;
            mouseColumn = criticalStack.top() % MAX_COLUMN;

↑如果走進死路，退回到上個岔路或起點（如果遇到岔路前就已經沒路了）。座標設成岔路的座標。

            // pop out things in the mouseStack until back to the top of criticalStack
            if (!mouseStack.empty())
            {
                while (mouseStack.top() != criticalStack.top())
                {
                    int curRow = mouseStack.top() / MAX_COLUMN;
                    int curCol = mouseStack.top() % MAX_COLUMN;
                    maze[curRow][curCol] = 8; // close the path after the critical point
                    mouseStack.pop();
                }
            }

↑老鼠回到上個岔路，那在通過岔路之後記錄在mouseStack的路線當然要回溯。
把所有要pop掉的座標都標記為8（死路）、pop，直到mouseStack回到岔路的座標。

            // delete the top of the critical point since it is dead end
            criticalStack.pop();
       
            // if all critical points are deleted, then there's no way out
            if (criticalStack.empty())
            {
                cout << "My mouse is STUCK!!! Be nice!" << endl;
                break;
            }
        }

↑把岔路也pop掉，再用while loop重新判斷有沒有岔路。
如果岔路都pop光了，表示連起點的座標都pop掉 = 無路可走。

== Second / Last Condition ==

單行道 / 岔路。
這條路除非是死路，否則可能就是最終的出路，因此先標記為3。
這項原本我設成兩個condition，但在寫blog的時候發現其實差別只在「有岔路時要把座標推進criticalStack」所以把它們整合成一個condition。

        else // form the single and multiple moves
        {
            maze[mouseRow][mouseColumn] = 3;
         
            // evaluate if the new step is the same as mouseStack.top
            if (!mouseStack.empty())
            {
                int current = mouseRow * MAX_COLUMN + mouseColumn;
                if (current != mouseStack.top())
                mouseStack.push(mouseRow * MAX_COLUMN + mouseColumn);
            }
            else
            mouseStack.push(mouseRow * MAX_COLUMN + mouseColumn);
         
            if (!isOnlyWay(east, west, north, south))
            criticalStack.push(mouseRow * MAX_COLUMN + mouseColumn);
         
            locateDir(east, west, north, south, mouseRow, mouseColumn);
        }
    }

↑為了防範重複push相同座標，設了if statement加以排除。
如果mouseStack是空的，就直接加進去了。
如果非「isOnlyWay」，代表有岔路，需要把座標推進criticalStack
然後用locateDir尋找下一步。
以上，主要的while loop結束。

     // make sure the mouse really escaped then print out the line
    if (mouseRow == 0 || mouseRow == (MAX_ROW - 1) || mouseColumn == 0 || mouseColumn == (MAX_COLUMN -1))
    {
        mouseStack.push(mouseRow * MAX_COLUMN + mouseColumn); // the last step escape!
        maze[mouseRow][mouseColumn] = 3;
        cout << "The cute mouse successfully escaped!" << endl;
    }

↑由於跳出的條件可能是1. 逃脫或2. 死路一條，所以要再用一個if來確認後，把最後一步推進mouseStack。

    // set the final array and its max
    int mouseSteps = mouseStack.size();
    int mazeSolution[mouseSteps];

↑設定要輸出的array，用mouseStack的大小來當array的大小。

    // copy mouseStack to a solution array
    for (int i = 0; i < mouseSteps; i++)
    {
        mazeSolution[mouseSteps - 1 - i] = mouseStack.top();
        mouseStack.pop();
    }

↑把mouseStack複製到array中。

    // print the solution in order
    for (int i = 0; i < mouseSteps; i++)
    {
        cout << mazeSolution[i] / MAX_COLUMN + 1 << ", " << mazeSolution[i] % MAX_COLUMN + 1<< endl;
    }

↑把array的值轉換回座標並顯示出來。

    // print the maze
    for (int i = 0; i < MAX_ROW; i++)
    {
        for (int j = 0; j < MAX_COLUMN; j++)
        {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }

↑顯示老鼠走過的迷宮，最終路徑會顯示3、走過且不通的路徑則是8。
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

以上，大功告成！