- it
- 1076. 迷宫问题
AcWing题目链接
带有路径的最短路径BFS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std
;
typedef pair
<int, int> PII
;
const int N
= 1e3+5;
int g
[N
][N
];
int dx
[]={1,-1,0,0};
int dy
[]={0,0,1,-1};
int n
;
PII pre
[N
][N
];
void bfs(int u
, int v
){
queue
<PII
> q
;
q
.push({u
, v
});
while(q
.size()){
PII t
= q
.front();
q
.pop();
for(int i
= 0; i
< 4; i
++){
int a
= t
.first
+ dx
[i
];
int b
= t
.second
+ dy
[i
];
if(a
< 0 || b
< 0||a
>= n
|| b
>=n
|| g
[a
][b
] == 1) continue;
g
[a
][b
] = 1;
pre
[a
][b
] = t
;
q
.push({a
, b
});
}
}
}
int main(){
scanf("%d", &n
);
for(int i
=0; i
< n
; i
++)
for(int j
= 0; j
< n
; j
++)
scanf("%d", &g
[i
][j
]);
bfs(n
-1,n
-1);
PII end
={0,0};
while(true){
printf("%d %d\n", end
.first
, end
.second
);
if(end
.first
== n
-1 && end
.second
== n
-1) break;
end
= pre
[end
.first
][end
.second
];
}
return 0;
}
