fork(1) download
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define mod 1000000007
  5. #define inf 100000000000000000
  6. #define ar array
  7. #define fast ios::sync_with_stdio(false); cin.tie(0)
  8. #define setpres(x) fixed<<setprecision(x)
  9. using namespace std;
  10. int m,n;
  11. string s[1000];
  12. int dx[]={0,0,-1,1};
  13. int dy[]={1,-1,0,0};
  14. queue<ar<int,2>> q;
  15. map<ar<int,2>,ar<int,2>> par;
  16. map<ar<int,2>,int> vis;
  17. string ans;
  18. bool ok(int i, int j)
  19. {
  20. return i>=0 && i<m && j>=0 && j<n && !vis[{i,j}] && s[i][j]!='#';
  21. }
  22. int32_t main()
  23. {
  24. cin>>m>>n;
  25. for(int i=0;i<m;i++)
  26. cin>>s[i];
  27. int ia,ib, fx,fy;
  28. for(int i=0;i<m;i++)
  29. {
  30. for(int j=0;j<n;j++)
  31. {
  32. if(s[i][j]=='A')
  33. {
  34. ia=i;
  35. ib=j;
  36. }
  37. if(s[i][j]=='B')
  38. {
  39. fx=i;
  40. fy=j;
  41. }
  42. }
  43. }
  44. par[{ia,ib}]={-1,-1};
  45. q.push({ia,ib});
  46. vis[{ia,ib}]=1;
  47. while(!q.empty())
  48. {
  49. auto x=q.front();
  50. q.pop();
  51. if(x[0]==fx && x[1]==fy)
  52. break;
  53. int i=x[0];
  54. int j=x[1];
  55. for(int k=0;k<4;k++)
  56. {
  57. if(ok(i+dx[k],j+dy[k]))
  58. {
  59. q.push({i+dx[k],j+dy[k]});
  60. vis[{i+dx[k],j+dy[k]}]=1;
  61. par[{i+dx[k],j+dy[k]}]={x[0],x[1]};
  62. }
  63. }
  64. }
  65. if(par.find({fx,fy})==par.end())
  66. {
  67. cout<<"NO";
  68. return 0;
  69. }
  70. cout<<"YES\n";
  71. while(1)
  72. {
  73. if(par[{fx,fy}][0]==-1)
  74. break;
  75. int f1=par[{fx,fy}][0];
  76. int f2=par[{fx,fy}][1];
  77. if(f2==fy+1)
  78. ans+='L';
  79. else if(f2==fy-1)
  80. ans+='R';
  81. else if(f1==fx+1)
  82. ans+='U';
  83. else
  84. ans+='D';
  85. fx=f1;
  86. fy=f2;
  87. }
  88. cout<<ans.length()<<"\n";
  89. for(int i=ans.length()-1;i>=0;i--)
  90. cout<<ans[i];
  91. }
Success #stdin #stdout 0.01s 4392KB
stdin
Standard input is empty
stdout
NO