2019年蓝桥杯迷宫问题
作者:
amagi
,
2023-03-19 20:18:36
,
所有人可见
,
阅读 134
#include <iostream>
#include <cstring>
using namespace std;
const int N = 70;
int m,n;
char x[N][N];
int y[N][N];
pair<int,int> w[N * N],q[N][N],e[N * N];
char ss[N * N];
void bfs(){
memset(y,-1,sizeof y);
y[1][1] = 0;
int h = 1,k = 1;
w[1] = {1,1};
int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
while(h <= k){
auto qq = w[h ++];
for (int i = 0; i <= 3; i ++ ) {
int xx = qq.first + dx[i];
int yy = qq.second + dy[i];
if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && y[xx][yy] == -1 && x[xx][yy] == '0'){
y[xx][yy] = y[qq.first][qq.second] + 1;
q[xx][yy] = qq;
w[++ k] = {xx,yy};
}
}
}
int x1 = m,y1 = n;
int u = 0;
while(x1 != 1 || y1 != 1){
u ++;
// cout << x1 << " " << y1 << endl;
e[u].first = x1;
e[u].second = y1;
auto pp = q[x1][y1];
x1 = pp.first;
y1 = pp.second;
}
u ++;
e[u].first = 1;
e[u].second = 1;
for(int i = u - 1;i >= 1; i -- ){
if(e[i].first - e[i + 1].first == 1) cout << "D";
if(e[i].first - e[i + 1].first == -1) cout << "U";
if(e[i].second - e[i + 1].second == 1) cout << "R";
if(e[i].second - e[i + 1].second == -1) cout << "L";
}
}
int main(){
scanf("%d %d\n",&m,&n);
for (int i = 1; i <= m; i ++ ) {
for (int j = 1; j <= n; j ++ ) scanf("%c",&x[i][j]);
scanf("\n");
}
// for (int i = 1; i <= m; i ++ ) {
// for (int j = 1; j <= n; j ++ ) printf("%c ",x[i][j]);
// printf("\n");
// }
bfs();
}