写给妹妹的编程札记 5 - 搜索: 迷宫问题 - 广度优先搜索

        让我们也使用广度优先搜索来解决一下迷宫问题，可以对比一下《写给妹妹的编程札记 4 - 搜索: 迷宫问题 - 深度优先搜索》。

        如在《写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索》中描述的广度优先搜索， 对一个简单的例子，我们手动进行一遍迷宫遍历。每次找到队首的搜索状态，把从这个状态开始的全部状态加入队列。

        广度优先搜索， 我们需要一个队列来维护访问过的搜索状态。 对于每个搜索状态，我们记录该状态对应迷宫中的位置currX/currY, 从上一个状态怎么过来的: prevDir, 上一个状态在队列中的位置prevState。 后面两个信息prevDir/prevState主要是为了反向找到路径。

typedef struct tagMazeState {int currX;int currY;int prevDir;int prevState;
} MazeState;

        除了新创建的队列，跟深度优先搜索一样， 我们需要记录一个位置是否访问过 - isVisited数组。

void Search(char** maze, int row, int col)
{    bool** isVisited;isVisited = new bool*[row];for(int i = 0; i < row; i++) {isVisited[i] = new bool[col];memset(isVisited[i], 0, sizeof(bool) * col);}MazeState* queue = new MazeState[row * col];int queueHead = 0;int queueTail = 0;MazeState origin;origin.currX     = 0;origin.currY     = 0;origin.prevDir   = -1;origin.prevState = -1;// 判断起点是否为空位if (maze[0][0] != '.') {printf("Invalid maze. Origin maze[0][0] is blocked!\n");return;}// 判断是否已经到达终点if (origin.currX == row - 1 && origin.currY == col - 1) {printf("Already arrive target position!\n");return;}queue[queueTail++] = origin;isVisited[0][0] = 1;BFS(maze, row, col, isVisited, queue, queueHead, queueTail);for(int i = 0; i < row; i++) delete[] isVisited[i];delete[] isVisited;delete[] queue;
}

        有了搜索状态队列的支持， 广度优先搜索的代码就很简单了：

void BFS(char** maze, int row, int col, bool** isVisited, MazeState* queue, int queueHead, int queueTail)
{// 判断队列是否为空while (queueHead < queueTail) {// 取出队首的搜索状态int currX = queue[queueHead].currX;int currY = queue[queueHead].currY;printf("queueHead: (%d, %d)\n", currX, currY);// 检查从这个状态开始的所有能够到达的状态 (广度优先搜索)for (int k = 0; k < 4; k++) {int nextX = currX + direction[k][0];int nextY = currY + direction[k][1];// 检查保证新位置在迷宫内，没有离开迷宫， 且是空位(不能走到墙里面)if ((nextX >= 0) && (nextX < row) && (nextY >= 0) && (nextY < col) && (maze[nextX][nextY] == '.')) {// 找到可以走的方向后， 需要判断这个新的位置是否已经走过，如果已经走过，我们继续会走就出现环路if (!isVisited[nextX][nextY]) {// 标记搜索访问过isVisited[nextX][nextY] = 1;// 没有走过的新位置，加入队列 (广度优先搜索)MazeState nextState;nextState.currX     = nextX;nextState.currY     = nextY;nextState.prevDir   = k;nextState.prevState = queueHead;queue[queueTail++]  = nextState;// 一旦发现目标状态到达的话， 说明已经找到最短路径，输出if (nextX == row - 1 && nextY == col - 1) {// 输出最短路径DisplayPath(queue, queueTail - 1);// 终止搜索return;}}}}// 队首的搜索状态已经完成，从队列中删除 (没有实际删除，还在queue数组中，只是不在逻辑队列中[queueHead, queueTail) )queueHead++;}
}

        跟深度优先搜索不同的是，我们采取广度优先，多条路径同时进行，不能只使用一个path数组保存当前的路径。 对应于搜索状态队列中的每一个状态， 其实都对应着一条从起点开始到该状态的一条路径。为了反向找到这条路径，搜索状态队列中的每个状态都已经记录了从哪个状态过来的，怎么过来的。 我们需要反向找到这条路径：

// 输出从起点开始到(queue[targetPositionIndex].currX, queue[targetPositionIndex].currY)的路径
void DisplayPath(MazeState* queue, int targetPositionIndex)
{// 终止条件。 起点的前一个状态index为：-1if (targetPositionIndex < 0) {return;}// 前一个状态int previousPositionIndex = queue[targetPositionIndex].prevState;// 从前一个状态怎么过来的int previousDirection     = queue[targetPositionIndex].prevDir;// 先输出从起点到前一个状态的路径DisplayPath(queue, previousPositionIndex);// 再输出从前一个状态到当前状态的路径switch(previousDirection) {case 0: printf("N"); break;case 1: printf("S"); break;case 2: printf("W"); break;case 3: printf("E"); break;}
}