Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define ull unsigned ll
- #define RV return void
- // #define inf 2000000000
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define Mini(x) *min_element(all(x))
- #define Maxi(x) *max_element(all(x))
- #define fixed(n) fixed << setprecision(n)
- #define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
- #define cin(v) for (auto&i:v) cin >> i;
- #define cout(v) for (auto&i:v) cout << i << " ";
- #define clr(memo, x) memset(memo, x, sizeof memo)
- #define updmin(a, b) a = min(a, b)
- #define updmax(a, b) a = max(a, b)
- #define vi vector < int >
- #define vl vector < ll >
- #define vc vector < char >
- #define vs vector < string >
- #define v2i vector < vector < int > >
- #define v2l vector < vector < int > >
- #define seti set < int >
- #define setl set < ll >
- #define mapii map < int , int >
- #define mapll map < ll , ll >
- #define mapli map < ll , int >
- #define mapci map < char , int >
- #define mapsi map < string , int >
- #define pll pair < ll , ll >
- #define pii pair < int , int >
- #define range(l,r,x) for(int i=l ; i < r ; i+=x)
- #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- vector < string > ternary= {"NO\n" , "YES\n"};
- void Zainab(){
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- /*================================ solution ================================ */
- const ll N = 1e3 + 5 , inf = 1e18;
- int n , m , X1 , X2 , Y1 , Y2 ;
- char arr[N][N];
- int dx[]={ -1 , 1 , 0 , 0 };
- int dy[]={ 0 , 0 , 1 , -1};
- char C[] ={ 'U' , 'D' , 'R' , 'L' };
- bool valid(int x , int y){
- return x >=0 and y>=0 and x < n and y < m ;
- }
- ll dp[N+10][N+10];
- ll rec(int x , int y ){
- if(x==X2 and y==Y2) return 0 ;
- if(!valid(x,y) or arr[x][y]=='#') return inf ;
- ll& ret = dp[x][y];
- if(~ret) return ret;
- ret = inf;
- for(int i =0 ; i < 4 ; i++){
- int newX = x + dx[i] , newY = y + dy[i];
- if(valid(newX , newY) and arr[newX][newY]!='#')
- ret = min(ret , 1+ rec(newX , newY));
- }
- return ret ;
- }
- void build(int x , int y ){
- if(x==X2 and y==Y2) return ;
- if(!valid(x,y) or arr[x][y]=='#') return ;
- ll ret = inf;
- for(int i =0 ; i < 4 ; i++){
- int newX = x + dx[i] , newY = y + dy[i];
- if(valid(newX , newY) and arr[newX][newY]!='#')
- ret = min(ret , 1 +rec(newX , newY));
- }
- for(int i =0 ; i < 4 ; i++){
- int newX = x + dx[i] , newY = y + dy[i];
- if(valid(newX , newY) and arr[newX][newY]!='#' and ret == 1 + rec(newX , newY)){
- cout << C[i];
- build(newX , newY);
- return ;
- }
- }
- }
- void myCode(){
- cin >> n >> m ;
- for(int i =0 ; i < n ; i++){
- for(int j =0 ; j < m ; j++){
- cin >> arr[i][j];
- if(arr[i][j]=='A') X1=i , Y1=j;
- else if(arr[i][j]=='B') X2 = i , Y2 = j;
- }
- }
- clr(dp , -1);
- ll ans = inf ;
- ans = min(ans , rec(X1 , Y1));
- if(ans == inf) RV(cout << "NO");
- cout << "YES\n" << ans << nl;
- build(X1,Y1);
- }
- int main(){
- FastCode ;
- Zainab() ;
- int testCase=1;
- // cin >> testCase ;
- for(int i=1 ; i<= testCase ; i++){
- myCode();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement