題目：

Description
定義一個二維數(shù)組： int maze[5][5]
= {0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,};
它表示一個迷宮克握，其中的1表示墻壁蕾管，0表示可以走的路，只能橫著走或豎著走菩暗，不能斜著走掰曾，要求編程序找出從左上角到右下角的最短路線。
Input
一個5 × 5的二維數(shù)組停团，表示一個迷宮旷坦。數(shù)據(jù)保證有唯一解。
Output
左上角到右下角的最短路徑佑稠，格式如樣例所示秒梅。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

題意很簡單，其實(shí)可以用廣搜舌胶。
問題在于如何模擬最短路徑捆蜀，其實(shí)我們可以在結(jié)構(gòu)體隊(duì)列中設(shè)一個記錄方向數(shù)組，這個數(shù)組中的元素記錄從 上個點(diǎn)到這個點(diǎn)需要通過什么方式（上下左右辆琅，因?yàn)闉榱藦V搜漱办，我們設(shè)了方向數(shù)組，用下標(biāo)代表上下左右）婉烟，沒走一步記錄一次。

參考代碼：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int mp[6][6];
bool vis[6][6];
int sx = 0, sy = 0, ex = 4, ey = 4;
int dx[4] = {-1, 1, 0, 0};//上下左右;
int dy[4] = {0, 0, -1, 1};
struct node {
    int x, y;
    int steps;
    int pt[30];//記錄從上一步到這一步需往哪里走;
} que[30];

void input() {
    for (int i = 0;i < 5;++i) {
        for (int j = 0;j < 5;++j) {
            cin >> mp[i][j];
        }
    }
    memset(vis, false, sizeof(vis));
}

void bfs() {
    node s;
    s.x = sx;
    s.y = sy;
    s.steps = 0;
    s.pt[s.steps] = 0;//還在起點(diǎn);
    int l = 0, r = 0;
    que[r++] = s;
    vis[sx][sy] = true;
    node p;
    while (l != r) {//隊(duì)列不為空;
        p = que[l++];
        if (p.x == ex && p.y == ey) {
            int xx = 0, yy = 0;
            cout << "(" << xx << ", " << yy << ")" << endl;
            for (int i = 1;i <= p.steps;++i) {
                 xx = xx + dx[p.pt[i]];
                 yy = yy + dy[p.pt[i]];
                //cout << "............" << dx[p.pt[i]] << endl;
                //cout << xx << " " << yy << endl;
                cout << "(" << xx << ", " << yy << ")" << endl;
            }
            return;
        }
        node q;
        for (int i = 0;i < 4;++i) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && mp[nx][ny] != 1 && !vis[nx][ny]) {
                q.x = nx;
                q.y = ny;
                q.steps = p.steps + 1;
                ////////////////
                for (int j = 0;j < p.steps;++j) {
                    q.pt[j] = p.pt[j];//將之前的路徑復(fù)制下來;
                }
                q.pt[q.steps] = i;//從p點(diǎn)到q點(diǎn)需要怎么走;//i = 0 : 上, i = 1 : 下, i = 2 : 左, i = 3 : 右;
                que[r++] = q;
                vis[nx][ny] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    bfs();
    return 0;
}