二下

資料結構｜HW2

3D立體迷宮問題

題目敘述

請根據所輸入的迷宮內容(包括迷宮層數、大小、迷宮圖、一起始點以及一終點)， 請顯示所有有可能的路徑(simple paths)數目(可往上、下、左或右方向走訪，以及往上下層移動)，此程式需能不斷輸入迷宮內容，並顯示其所有有可能的路徑數目，直到輸入的迷宮大小邊長小於或等於 0。

PS. Simple path 為一路徑，且路徑中的節點不會重複。

輸入格式為(z, y, x)，且z從1開始。

答題思路

此類迷宮問題常見的解法是使用Flood fill演算法。

這個問題本質上就是一個路徑搜索問題。而筆者採用的方式稱為深度優先搜尋，使用遞迴並搭配堆疊的方式就能夠輕鬆實現。

參考答案 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <iostream>
#include <tuple>
#include <vector>
#include <stack>

using namespace std;
using Maze = vector<vector<vector <int>>>;
using Pos = tuple<int, int, int>;
using Path = stack<Pos>;

int ans = 0;
int l, w, h;    // 長寬高
Pos target;     // 終點

void func(Path& path, Maze &maze) {
    if(path.top() == target) {
        ans += 1;
        return;
    }
    
    auto &[z, y, x] = path.top();       // 當前座標
    maze[z][y][x] = 1;                  // 走過的地方標記為1

    // 上下左右前後
    for(int i=0; i<6; i++) {
        int dz = 0, dy = 0, dx = 0;
        switch(i) {
            case 0: dz = 1; break;
            case 1: dz = -1; break;
            case 2: dy = 1; break;
            case 3: dy = -1; break;
            case 4: dx = 1; break;
            case 5: dx = -1; break;
        }
        
        int nz = z + dz;
        int ny = y + dy;
        int nx = x + dx;
        
        if(nz >= 0 && nz < h && ny >= 0 && ny < w && nx >= 0 && nx < l) {
            if(maze[nz][ny][nx] == 0) {
                path.emplace(nz, ny, nx);
                func(path, maze);
                path.pop();
            }
        }
    }
    maze[z][y][x] = 0;

    return;
}

int main() {
    int wall;           // 牆壁
    int x, y, z;        // 座標
    
    while(cin >> h >> w >> l && (h != 0 && w != 0 && l != 0)) {
        // 記錄迷宮地形
        Maze maze(h, std::vector<std::vector<int>>(w, std::vector<int>(l, 1)));
        Path path;      // 記錄走過路徑

        for(z=0; z<h; z++) {
            for(y=0; y<w; y++) {
                for(x=0; x<l; x++) {
                    cin >> wall;
                    maze[z][y][x] = wall;
                }
            }
        }
        
        cin >> z >> y >> x;
        path.emplace(z-1, y, x);
        
        cin >> z >> y >> x;
        target = make_tuple(z-1, y, x);
        
        func(path, maze);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}