总时间限制: 1000ms 内存限制: 65536kB

描述

定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个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

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路

基础广搜. 先将起始位置入队.

每次从队列拿出一个元素, 扩展其相邻的4个元素入队列(要判重), 直到队头元素为终点为止.

队列的元素要记录指向父节点的指针(因为题目要输出路径).

本题不能用STL的 queue 或 deque, 我们得自己写一个简单队列, 用两个指针(一个指向队头, 一个指向队尾)来维护.

代码如下：

#include <iostream>
#include <cstring>
using namespace std;
int maze[8][8];
int visited[8][8];    // 判重
int xAxis[4] = {-1, 1, 0, 0};  // 横坐标4个方向
int yAxis[4] = {0, 0, -1, 1};  // 纵坐标4个方向
typedef struct Node {
    int row;
    int col;
    int parentIndex;
}Node;
bool isValidNode(int x, int y) {
    if( x < 0 || x >= 5 || y < 0 || y >= 5) // 超过迷宫边界?
        return false;
    if( visited[x][y] == 0x1 )  // 此节点被访问过了吗?
        return false;
    if( maze[x][y] == 0x1 )  // 此节点是围墙吗?
        return false;
    return true;
}
int BFS(Node* queue, int head, int tail) {
    while( head != tail ) {
        Node tmpHead = queue[head];
        if(tmpHead.row == 4 && tmpHead.col == 4) {  // 到终点了
            return head;
        }
        for(int i = 0; i < 4; i++) {  // 遍历4个方向
            int xx = tmpHead.row + xAxis[i];
            int yy = tmpHead.col + yAxis[i];
            if( isValidNode(xx, yy) ) {
                queue[tail].row = xx;
                queue[tail].col = yy;
                queue[tail].parentIndex = head;
                visited[xx][yy] = 0x1;
                tail++;
            }
        }
        head++;     // 队首节点出队
    }   
    return head;
}
void PrintPath(Node* queue, int head) {     // 递归打印路径, 省去反转链表的操作
    if( head == 0 )
        printf("(0, 0)\n");
    else {
        if( queue[head].parentIndex != -1 ) {
            PrintPath(queue, queue[head].parentIndex);
            printf("(%d, %d)\n", queue[head].row, queue[head].col);
        }
    }
}
int main() {
    /* Read data and initialize */
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            cin >> maze[i][j];
        }
    }
    memset(visited, 0x0, sizeof(visited));
    /* Create a  queue */
    Node* queue = new Node[30];
    int queueHead = 0, queueTail = 0;
    /* Src node join queue */
    queue[0].row = 0;
    queue[0].col = 0;
    queue[0].parentIndex = -1;  // parent is itself
    visited[0][0] = 0x1;
    queueTail++;
    /* BFS and display result */
    int result = BFS(queue, queueHead, queueTail);
    PrintPath(queue, result);
    return 0;
}