广度优先搜索：走迷宫

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef struct
{
    int r;
    int c;
    int step;
}LOC;//点的属性

typedef struct
{
    int sr, sc, er, ec;
}POR;//传送门的属性

char buf[1000];
char map[101][101];//地图
int N, M, W;
queue<LOC> Q;//点的队列
vector<POR> P;//存储所有的传送门信息
int sr, sc, er, ec;//start, end, row, col
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//代表四个方向

void addLOC(int r, int c, int step)
{
    LOC tmp;
    tmp.c = c;
    tmp.r = r;
    tmp.step = step;
    Q.push(tmp);
    map[r][c] = '2';
}//在队列中添加一个点，并在地图上留下标记‘2’，防止重复（0表示可以走，1表示墙，2表示走过）

void solve()
{
    int i;
    addLOC(sr, sc, 0);//添加第一个点（起点）
here:
    while(!Q.empty())
    {
        LOC cur = Q.front();//提取这个点的信息
        Q.pop();//处理后便可以退出队列
        if(cur.c == ec && cur.r == er)
        {
            cout << cur.step << endl;
            return;
        }//如果到达终点，就输出当前的步数
        for(i = 0; i < W; ++i)
        {
            if(P[i].sr == cur.r && P[i].sc == cur.c)
            {
                if(map[P[i].er][P[i].ec] == '0')
                    addLOC(P[i].er, P[i].ec, cur.step+1);
                goto here;
            }
        }//遍历传送门，如果踩到了，而且传送到的地方不是墙也没有走过，就添加这个点，继续看队列中的下一个点
        //否则此路不通，看队列中的下一个点
        int tmpr, tmpc, i;
        for(i = 0; i < 4; ++i)
        {
            tmpr = cur.r+dir[i][0];
            tmpc = cur.c+dir[i][1];
            if(tmpr>=0 && tmpr<N && tmpc>=0 && tmpc<M && map[tmpr][tmpc]=='0')
            {
                addLOC(tmpr, tmpc, cur.step+1);
            }
        }//尝试四个方向，如果某个方向有路（不是墙也没有到地图外也没有走过），就添加这个点
    }
    cout << "die" << endl;//如果一直都没有return，输出die
}
//广度优先搜索，使用队列实现

int main()
{
    //freopen("data.txt", "r", stdin);
    int num, i;
    cin >> num;
    while(num--)
    {
        P.clear();//把上一个case的陷阱信息置空
        while(!Q.empty())
            Q.pop();//把上一个case的点的队列置空置空
        cin >> N >> M;//输入行和列数
        gets(buf);//吃掉回车
        for(i = 0; i < N; ++i)
            gets(map[i]);//读入地图
        cin >> W;//传送门个数
        for(i = 0; i < W; ++i)
        {
            POR tmp;
            cin >> tmp.sr >> tmp.sc >> tmp.er >> tmp.ec;
            P.push_back(tmp);
        }//读入传送门并把它加入数组
        cin >> sr >> sc >> er >> ec;//输入起点和终点的行，列
        solve();//调用函数解决迷宫
    }
    return 0;
}

solve()函数采用深度优先搜索算法，遍历离当前点最近的点（或传送门到达的点）加入队列，被加入的点在与“推出它的点”同步数的点被处理完之前都不会被处理，换句话说，处理一个点过后可能会在队尾加入数个点（也可能不加入），加入后需要做的是继续提取队头的点进行操作。广度优先可以想象为河流的分流过程。