本文主要是介绍写给妹妹的编程札记 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++;}
}
// 输出从起点开始到(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;}
}
这篇关于写给妹妹的编程札记 5 - 搜索: 迷宫问题 - 广度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!