深圳工信部网站备案信息查询,wordpress维护,安徽建网站公司,深圳4a广告公司题目描述#xff1a;sun所在学校每年都要举行电脑节#xff0c;今年电脑节有一个新的趣味比赛项目叫做闯迷宫。 sun的室友在帮电脑节设计迷宫#xff0c;所以室友就请sun帮忙计算下走出迷宫的最少步数。 知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的… 题目描述 sun所在学校每年都要举行电脑节今年电脑节有一个新的趣味比赛项目叫做闯迷宫。 sun的室友在帮电脑节设计迷宫所以室友就请sun帮忙计算下走出迷宫的最少步数。 知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的map。 比赛规则是从原点0,0开始走到终点n-1,n-1只能上下左右4个方向走只能在给定的矩阵里走。 输入 输入有多组数据。 每组数据输入n0n100然后输入n*n的01矩阵0代表该格子没有障碍为1表示有障碍物。 注意如果输入中的原点和终点为1则这个迷宫是不可达的。 输出 对每组输入输出该迷宫的最短步数若不能到达则输出-1。 样例输入 2
0 1
0 0
5
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
0 1 1 1 0
1 0 1 0 0 样例输出 2
8 核心代码百度 structNode
{
intx;
inty;
intstep;
Node(intx1,inty1,intstep1):x(x1),y(y1),step(step1){}
};
intBFS()
{
Nodenode(0,0,0);
queueNodeq;
while(!q.empty())q.pop();
q.push(node);
while(!q.empty())
{
nodeq.front();
q.pop();
if(node.xn-1node.yn-1)
{
returnnode.step;
}
visit[node.x][node.y]1;
for(inti0;i4;i)
{
intxnode.xstepArr[i][0];
intynode.ystepArr[i][1];
if(x0y0xnynvisit[x][y]0mazeArr[x][y]0)
{
visit[x][y]1;
Nodenext(x,y,node.step1);
q.push(next);
}
}
}
return-1;
}
