题目描述
给定一个 n×n 的二维数组,如下所示:
int maze[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,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含 n 个整数 0 或 1,表示迷宫。
输出格式
输出从左上角到右下角的最短路线,如果答案不唯一,输出任意一条路径均可。
按顺序,每行输出一个路径中经过的单元格的坐标,左上角坐标为 (0,0),右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
样例
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
算法1
(bfs+dfs) $O(n^2)$
先使用bfs得出所有点与起点的最短距离
(为方便不妨让起点与自身的距离为1)
从终点使用dfs 打印其中的一条最短路径
时间复杂度
时间复杂度来自于bfs
dfs打印的复杂度为O(n)
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
using PII=pair<int,int>;
const int N=1005;
int a[N][N];
int n;
void bfs(){
queue<PII> q;
q.push({0,0});
a[0][0]=1;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
int cnt=1;
while(q.size()){
int t=q.size();
cnt++;
while(t--){
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<n&&!a[nx][ny]){
q.push({nx,ny});
a[nx][ny]=cnt;
}
}
}
}
}
void dfs(int x,int y){
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<n&&a[nx][ny]==a[x][y]-1){
dfs(nx,ny);
break;
}
}
cout<<x<<' '<<y<<'\n';
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
if(a[i][j]) a[i][j]=0x7f7f7f7f;
}
}
bfs();
dfs(n-1,n-1);
return 0;
}