Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Homework 2

Data Structures

 

Input: maze.in.txt

Output: maze.out.txt

 

Problem description:

       此作業為老鼠走迷宮，迷宮配置圖在 maze.in.txt 裡，請同學自行讀入資料，0代表可以走的路徑，1代表圍牆。請使用 stack 來解決問題，以C/C++來撰寫你的程式，這裡限定你的老鼠只能往上、下、左、右走，不考慮斜的方向

 

Sample Output:

       印出所有你發現的路徑，使用 ”*” 標示出來。舉例來說，假設是4X5的迷宮，入口是(1,1)，出口是(4,5)，然後你的輸出檔是 maze.out.txt ，就像以下所呈現的：

* * * 1 0

1 1 * 1 0

0 1 * 1 1

0 1 * * *

請繳交 .cpp或 .c和 .exe檔就好，繳交格式：學號_姓名_HW2.cpp/.exe (ex: 1015XXXXX_助教_HW2.cpp/.exe)

---

Sample Input :

0 0 0 0 0 0 0

0 1 1 1 0 1 0

0 1 0 0 1 0 0

0 1 0 1 0 1 0

0 0 0 0 0 1 0

1 0 1 1 0 1 1

0 0 0 1 0 0 0

Sample Output:

* 0 0 0 0 0 0

* 1 1 1 0 1 0

* 1 0 0 1 0 0

* 1 0 1 0 1 0

* * * * * 1 0

1 0 1 1 * 1 1

0 0 0 1 * * *

Sample Input :
0 0 0 0
0 0 1 0
1 0 1 0
1 0 0 0

Sample Output:

* * * *
* * 1 *
1 0 1 *
1 0 0 *

* 0 0 0
* * 1 0
1 * 1 0
1 * * *

* * 0 0
0 * 1 0
1 * 1 0
1 * * *

* * * *
0 0 1 *
1 0 1 *
1 0 0 *

---

#include <cstdio>
#include <fstream>
#include <sstream>
#include <iostream>
#define maxN 105
using namespace std;
template <typename T>
struct Node {
    T d;
    Node *prev;
};
template <class T>
class STACK {
    public:
        STACK() {
            idx = NULL;
            SIZE = 0;
        }
        T top() {
            T cpy = idx->d;
            return cpy;
        }
        void pop() {
            Node<T> *tmp;
            tmp = idx;
            idx = idx->prev;
            delete tmp;
            SIZE--;
        }
        void push(T item) {
            Node<T> *nd = new Node<T>;
            nd->d = item;
            nd->prev = idx;
            idx = nd;
            SIZE++;
        }
        bool empty() {
            return idx == NULL;
        }
        int size() {
            return SIZE;
        }
    private:
        Node<T> *idx;
        int SIZE;
};
struct state {
    int x, y, p;
    void init(int tx, int ty, int tp) {
        x = tx, y = ty, p = tp;
    }
};
void solve(int g[][maxN], int n, int m) {
    n--, m--;
    STACK<state> stk;
    state tn, ch, call;
    tn.init(0,0,0);
    stk.push(tn);
    int used[105][105] = {}, way[105][105] = {};
    int tx, ty, i, j;
    used[0][0] = way[0][0] = 1;
    while(!stk.empty()) {
        tn = stk.top();
        tx = tn.x, ty = tn.y;
        if(!tn.p) tx--;
        else if(tn.p == 1)  tx++;
        else if(tn.p == 2)  ty--;
        else if(tn.p == 3)  ty++;
        else {
            used[tx][ty] = way[tx][ty] = 0;
            stk.pop();
            continue;
        }
        ch = tn, ch.p++;
        stk.pop(), stk.push(ch);
        if(tx < 0 || ty < 0 || tx > n || ty > m)
            continue;
        if(used[tx][ty] || g[tx][ty])    continue;
        used[tx][ty] = way[tx][ty] = 1;
        call.x = tx, call.y = ty, call.p = 0;
        stk.push(call);
        if(tx == n && ty == m) {
            for(i = 0; i <= n; i++, puts(""))
                for(j = 0; j <= m; j++)
                    printf("%c ", way[i][j] ? '*' : g[i][j]+'0');
            puts("");
        }
    }
}
int main() {
    freopen("maze.in.txt", "r", stdin);
    freopen("maze.out.txt", "w", stdout);
    string line;
    int n = 0, m;
    int g[maxN][maxN];
    while(getline(cin, line)) {
        stringstream sin(line);
        m = 0;
        while(sin >> g[n][m])
            m++;
        n++;
    }
    solve(g, n, m);
    return 0;
}