本文主要是介绍题目1335：闯迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
sun所在学校每年都要举行电脑节，今年电脑节有一个新的趣味比赛项目叫做闯迷宫。
sun的室友在帮电脑节设计迷宫，所以室友就请sun帮忙计算下走出迷宫的最少步数。
知道了最少步数就可以辅助控制比赛难度以及去掉一些没有路径到达终点的map。
比赛规则是：从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走。
- 输入：
-
输入有多组数据。
每组数据输入n（0<n<=100），然后输入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
使用BFS算法并记下遍历的层数就好了。
C++代码：
#include<stdio.h>
#include<stdlib.h>int A[100][100];
int point[100*100][2];
bool flag[100][100];
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int bfs(int n){int head=0,tail=0,step=0;if(A[0][0]==1||A[n-1][n-1]==1)return -1;if(n==1&&A[0][0]==0)return 0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)flag[i][j]=true;point[tail][0]=0;point[tail][1]=0;flag[0][0]=false;tail++;int t=0;while(tail>head){int currentx=point[head][0];int currenty=point[head][1];for(int i=0;i<4;i++){int tempx=currentx+move[i][0];int tempy=currenty+move[i][1];if(tempx==n-1&&tempy==n-1)return step+1;if((tempx>=0&&tempx<n&&tempy>=0&&tempy<n)&&flag[tempx][tempy]&&(A[tempx][tempy]==0)){point[tail][0]=tempx;point[tail][1]=tempy;flag[tempx][tempy]=false;tail++;}}if(head==t){step++;t=tail-1;}head++;}return -1;
}
int main(){int n;//freopen("1.txt","r",stdin);while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&A[i][j]);printf("%d\n",bfs(n));}return 0;
}这篇关于题目1335：闯迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
