可以浏览的外文网站,新媒体营销策划,加强门户网站建设与管理办法,ui培训一般多少钱给定一个 nm 的二维整数数组#xff0c;用来表示一个迷宫#xff0c;数组中只包含 0 或 1#xff0c;其中 0 表示可以走的路#xff0c;1 表示不可通过的墙壁。
最初#xff0c;有一个人位于左上角 (1,1)处#xff0c;已知该人每次可以向上、下、左、右任意一个方向移动…给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。
最初有一个人位于左上角 (1,1)处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问该人从左上角移动至右下角 (n,m) 处至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行每行包含 m 个整数00 或 11表示完整的二维数组迷宫。
输出格式
输出一个整数表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例
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输出样例
8
思路从起始点出发每次找它旁边的能走的点上下左右四个方向然后再从新找到的点找旁边能走的点依次类推直到找到终点为止这里我们用一个队列去实现先将起点入队然后当队列不为空的时候每次取出队头的点找出队头旁边的点将旁边能走的点且第一次找到入队这样就能一直找找到终点。
BFS就是把这一层全部搜完才会搜下一层因此它第一次搜到的点就是该点离起始点最近的时候适合用来解决求最小步数最少操作几次等最短路问题。 找的顺序如下图所示 可以看到在图上的例子里面我们找了八次找到了终点也就是终点到起点的距离为8。
如何实现找出队头旁边的点 int dx[4]{-1,1,0,0}, dy[4]{0,0,-1,1}; //用向量表示点走四个方向后的变化分别是上下左右while(q.size()){PII tq.front(); //得到队头q.pop(); //删掉队头和上面的代码加起来就是取出队头for(int i0;i4;i) //队头的点依次走四个方向{int xt.firstdx[i];int yt.seconddy[i];//点在边界内且点可以走且点是第一次被找到if(x0 xn y0 ym g[x][y]0 d[x][y]-1){d[x][y]d[t.first][t.second]1; //每次找的是它的上下左右的点且不会找已经走过的点所以找到的点离起点的距离就又远了1q.push({x,y}); //把这个新找到的点放进队伍中}}}用dx和dy数组表示上下左右四个方向移动后点坐标的变化这里的坐标(x,y)表示的是x行y列向上就是x-1y不变我们把它放进dx和dy的第一个元素里写为-1和0 int dx[4]{-1,1,0,0}, dy[4]{0,0,-1,1}; //用向量表示点走四个方向后的变化分别是上下左右
四个方向的变化如下图所示 示例代码
#includeiostream
#includequeue
#includecstring
using namespace std;typedef pairint,int PII; //这个主要是方便队列存放点的坐标所以需要一对int
const int N 100;
int n,m;
int g[N][N]; //存储地图
int d[N][N]; //存储每一个点到起点的距离int bfs()
{queuePII q;memset(d,-1,sizeof(d)); //初始全部设为-1表示全没走过d[0][0]0; //起始点到起点的距离为0q.push({0,0}); //第一个点入队int dx[4]{-1,1,0,0}, dy[4]{0,0,-1,1}; //用向量表示点走四个方向后的变化分别是上下左右while(q.size()){PII tq.front(); //得到队头q.pop(); //删掉队头和上面的代码加起来就是取出队头for(int i0;i4;i) //队头的点依次走四个方向{int xt.firstdx[i];int yt.seconddy[i];//沿着这个方向走点在边界内并且这个点可以走(g[x][y]0)这个点还没有走过d[x][y]-1第一次搜到的点才是最短距离if(x0 xn y0 ym g[x][y]0 d[x][y]-1){d[x][y]d[t.first][t.second]1; //每次找的是它的上下左右的点且不会找已经走过的点所以找到的点离起点的距离就又远了1q.push({x,y}); //把这个新找到的点放进队伍中}}}return d[n-1][m-1]; //输出到右下角的点终点的最短距离
}
int main()
{cinnm;for(int i0;in;i){for(int j0;jm;j){cing[i][j];}}coutbfs()endl;return 0;
}
