给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成,每一步可以向领接的上下左右四格的通道移动。请求出起点到终点所需的最小步数。
请注意,本题假定从起点一定可以移动到终点。
限制条件 N,M ≤ 100
思路:
借助辅助数组来标记当前位置是否走过,首先将辅助数组全部初始化为INF
定义一个pair,用来装坐标x,y,然后用pair存入队列
首先把开始位置加入队列中,然后把map中开始位置置为0
当队列不为空的时候,取队列头部的pair,然后做一个判断,看当前坐标是否为终点的坐标,如果是就break退出
开始上下左右四个方向的循环遍历,如果当前地图上的值不是#,而且辅助数组是默认值INF的时候,就加入队列。
然后辅助数组中的当前坐标的值变成 前一个出队列的辅助数组坐标中的值 加 1
最后返回辅助数组中终点坐标的值
const int INF = 1000000; typedef pair<int, int> P; int sx = 0, sy = 1; int gx = 9, gy = 8; int N = 10, M = 10; int map[10][10]; int dx[] = { 1,0,-1,0 }; int dy[] = { 0,1,0,-1 }; int maze[10][10] = { {‘#‘,‘S‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘.‘,‘#‘}, {‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘#‘,‘.‘,‘.‘,‘#‘}, {‘.‘,‘#‘,‘.‘,‘#‘,‘#‘,‘.‘,‘#‘,‘#‘,‘.‘,‘#‘}, {‘.‘,‘#‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘#‘,‘#‘,‘.‘,‘#‘,‘#‘,‘.‘,‘#‘,‘#‘,‘#‘,‘#‘}, {‘.‘,‘.‘,‘.‘,‘.‘,‘#‘,‘.‘,‘.‘,‘.‘,‘.‘,‘#‘}, {‘.‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘.‘,‘#‘}, {‘.‘,‘.‘,‘.‘,‘.‘,‘#‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘.‘,‘#‘,‘#‘,‘#‘,‘#‘,‘.‘,‘#‘,‘#‘,‘#‘,‘.‘}, {‘.‘,‘.‘,‘.‘,‘.‘,‘#‘,‘.‘,‘.‘,‘.‘,‘G‘,‘#‘} }; int bfs() { queue<P> q; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = INF; } } q.push(P(sx, sy)); map[sx][sy] = 0; while (!q.empty()) { P p = q.front(); q.pop(); if (p.first == gx && p.second == gy) { break; } for (int i = 0; i < 4; i++) { int nx = p.first + dx[i]; int ny = p.second + dy[i]; if (nx >= 0 && nx < N&&ny >= 0 && ny < M&&maze[nx][ny] != ‘#‘&&map[nx][ny] == INF) { q.push(P(nx, ny)); map[nx][ny] = map[p.first][p.second] + 1; } } } return map[gx][gy]; }
原文:https://www.cnblogs.com/yuanjun93/p/13828563.html