Morris' Blog

2012-10-23 20:24:27Morris

[資料結構][HW] 走迷宮 STACK 找出所有路徑

留言 1 收藏 0 推薦 0

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;
}

上一篇：[練習] 打出垃圾碼，以 BrainFuck 為例

下一篇：[演算法][程式作業] Edit distance