問題鏈接：CCF201604試題。

問題描述：

  小明在玩一個電腦游戲，游戲在一個n×m的方格圖上進行，小明控制的角色開始的時候站在第一行第一列，目標是前往第n行第m列。　　方格圖上有一些方格是始終安全的，有一些在一段時間是危險的，如果小明控制的角色到達一個方格的時候方格是危險的，則小明輸掉了游戲，如果小明的角色到達了第n行第m列，則小明過關。第一行第一列和第n行第m列永遠都是安全的?！　∶總€單位時間，小明的角色必須向上下左右四個方向相鄰的方格中的一個移動一格?！　〗涍^很多次嘗試，小明掌握了方格圖的安全和危險的規律：每一個方格出現危險的時間一定是連續的。并且，小明還掌握了每個方格在哪段時間是危險的?！　‖F在，小明想知道，自己最快經過幾個時間單位可以達到第n行第m列過關。

　　輸入的第一行包含三個整數n, m, t，用一個空格分隔，表示方格圖的行數n、列數m，以及方格圖中有危險的方格數量?！　〗酉聛韙行，每行4個整數r, c, a, b，表示第r行第c列的方格在第a個時刻到第b個時刻之間是危險的，包括a和b。游戲開始時的時刻為0。輸入數據保證r和c不同時為1，而且當r為n時c不為m。一個方格只有一段時間是危險的（或者說不會出現兩行擁有相同的r和c）。

　　輸出一個整數，表示小明最快經過幾個時間單位可以過關。輸入數據保證小明一定可以過關。問題分析：這是一個求最短路徑的問題，即求最優問題，通常用BFS（廣度優先搜索）來實現。本題也用BFS來實現，比較難以考慮到的是，需要一個三維的標志來避免重復搜索。除了行列坐標外，還需要考慮時間因素，所以是三維的。因為一些格在某個時間范圍是危險的，不可進入，但是這個時間范圍之外，是可以隨意進入的。所以有時候需要在一些地方踱步，等過了這段時間再前行，就不能簡單地限制為進入過的格不能再進入。

程序說明：把格的危險時間范圍存儲在數組visited[][][]中，使得程序邏輯變得更加簡潔，同時也節省了存儲。其他都是套路。

提交后得100分的C++語言程序如下：

/* CCF201604-4 游戲 */#include <iostream>#include <cstring>#include <queue>using namespace std;const int N = 100;const int DIRECTSIZE = 4;struct direct {    int drow, dcol;} direct[DIRECTSIZE] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int visited[N+1][N+1][300+1];struct node {    int row, col, level;};int bfs(int n, int m){    node start, front, v;    start.row = 1;    start.col = 1;    start.level = 0;    queue<node> q;    q.push(start);    while(!q.empty()) {        front = q.front();        q.pop();        // 到達終點則結束        if(front.row == n && front.col == m)            return front.level;        for(int i=0; i<DIRECTSIZE; i++) {            // 移動一格            v.row = front.row + direct[i].drow;            v.col = front.col + direct[i].dcol;            v.level = front.level + 1;            // 行列越界則跳過            if(v.row < 1 || v.row > n || v.col < 1 || v.col > m)                continue;            // 已經訪問過的點不再訪問            if(visited[v.row][v.col][v.level])                continue;            // 向前搜索：標記v點為已經訪問過，v點加入隊列中            visited[v.row][v.col][v.level] = 1;            q.push(v);        }    }    return 0;}int main(){    int n, m, t, r, c, a, b;    // 變量初始化    memset(visited, 0, sizeof(visited));    // 輸入數據    cin >> n >> m >> t;    for(int i=1; i<=t; i++) {        cin >> r >> c >> a >> b;        // 設置方格危險時間，使之那些時間不可進入        for(int j=a; j<=b; j++)            visited[r][c][j] = 1;    }    // BFS搜索    int ans = bfs(n, m);    // 輸出結果    cout << ans << endl;    return 0;}