CSES - Labyrinth | Mê cung
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho bản đồ của một mê cung, nhiệm vụ của bạn là tìm ra một đường đi từ vị trí bắt đầu đến vị trí kết thúc. Bạn có thể đi sang trái, phải, lên trên và xuống dưới.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
- \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả mê cung. Mỗi ký tự là
.(sàn),#(tường),A(bắt đầu) hoặcB(kết thúc).
Output
- Đầu tiên in
YESnếu tồn tại đường đi vàNOnếu ngược lại. - Nếu có đường đi, dòng tiếp theo in độ dài của đường đi ngắn nhất. Và dòng cuối in mô tả của đường đi đó dưới dạng một xâu bao gồm các ký tự
L(trái),R(phải),U(lên) vàD(xuống). Bạn có thể in bất kỳ giải pháp hợp lệ nào.
Constraints
- \(1 \leq n, m \leq 1000\)
Example
Sample input
5 8
########
#.A#...#
#.##.#B#
#......#
########
Sample output
YES
9
LDDRRRRRU
Bình luận
Hint C++
ko chép code nha mục đích là tham khảo
include<bits/stdc++.h>
using namespace std;
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
define error(args...)
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}
define int long long
define pb push_back
define F first
define S second
define ll long long
define ull unsigned long long
define ld long double
define pii pair<int,int>
define vi vector<int>
define vii vector<pii>
define vc vector
define L cout<<'\n';
define E cerr<<'\n';
define all(x) x.begin(),x.end()
define rep(i,a,b) for (int i=a; i<b; ++i)
define rev(i,a,b) for (int i=a; i>b; --i)
define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
define setpr(x) cout<<setprecision(x)<<fixed
define sz size()
define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
const ll inf = INT_MAX;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const ll md = 1000000007;
int vis[1000005]={0};
vi adj[1000005];
queue<int> q;
int par[1000005];
bool bfs(int s){
vis[s]=1;
q.push(s);
while(!q.empty()){
int s = q.front(); q.pop();
for( auto i: adj[s]){
if (vis[i]) continue;
vis[i]=vis[s]+1;
par[i]=s;
q.push(i);
}
}
return 0;
}
void solve(){
int n,m; see(n,m);
char grid[n][m];
int st=0, end=0;
rep(i,0,n){
rep(j,0,m){
int z = i*m+j;
see(grid[i][j]);
if (grid[i][j]=='#') continue;
if (grid[i][j]=='A') st=z;
if (grid[i][j]=='B') end=z;
if (i>=1 && grid[i-1][j]!='#') adj[z].pb(z-m), adj[z-m].pb(z);
if (j>=1 && grid[i][j-1]!='#') adj[z].pb(z-1), adj[z-1].pb(z);
}
}
bfs(st);
if (!vis[end]){put("NO"); return;}
vi v; int i = end;
while (i!=st){
v.pb(i);i=par[i];
}
putl("YES");putl(v.sz);
int x = st/m, y = st%m;
string ans="";
rev(i,v.sz-1,-1){
int x1 = v[i]/m, y1 = v[i]%m;
if (x==x1) ans+=(y>y1?'L':'R');
else ans+=(x>x1?'U':'D');
x = x1, y = y1;
}
put(ans);
}
signed main(){
IOS;
#ifdef LOCAL
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w", stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
//cout<<'\n';
}
#ifdef LOCAL
clock_t tStart = clock();
cerr<<fixed<<setprecision(10)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
#endif
}
ADMIN cho chúng em xin 0.5s nữa cho python với ạ
không đủ thời gian cho python 🙂
???
vì tôi gà
truy vết đường đi như nào nhỉ?
Note
Các bạn có thể để chế độ tiếng Việt để bài tự dịch sang tiếng Việt
admin sửa lại test mẫu giúp em được không ạ, đáng lẽ dòng tiếp theo nó phải xuất đường đi như trong output chứ!