fork download
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<string> mat;
  7. char dir[1001][1001];
  8. long long visited[1001][1001];
  9.  
  10. struct node
  11. {
  12. long long x,y;
  13. node(long long x1,long long y1)
  14. {
  15. x=x1;
  16. y=y1;
  17. }
  18. };
  19.  
  20. long long rows[]={0,1,0,-1};
  21. long long cols[]={1,0,-1,0};
  22. char d[] = {'R','D','L','U'};
  23.  
  24. bool isValid(long long x,long long y,long long n,long long m)
  25. {
  26. return x>=0 && y>=0 && x<n && y<m;
  27. }
  28.  
  29. int main() {
  30.  
  31. long long n,m;
  32. cin>>n>>m;
  33.  
  34. long long starti,startj,endi,endj;
  35.  
  36. for(long long i=0;i<n;i++)
  37. {
  38. string x;
  39. cin>>x;
  40. mat.push_back(x);
  41. }
  42.  
  43. for(long long i=0;i<n;i++)
  44. {
  45. //cout<<mat[i]<<endl;
  46. for(long long j=0;j<m;j++)
  47. {
  48. if(mat[i][j] == 'A')
  49. {
  50. starti=i;
  51. startj=j;
  52. }
  53. if(mat[i][j] == 'B')
  54. {
  55. endi=i;
  56. endj=j;
  57. }
  58. dir[i][j] = 'X';
  59. visited[i][j] = 0;
  60. }
  61. }
  62.  
  63. queue<node*> Q;
  64. Q.push(new node(starti,startj));
  65.  
  66. //cout<<"starti="<<starti<<" startj="<<startj<<endl;
  67. //cout<<"endi="<<endi<<" endj="<<endj<<endl;
  68. long long flag=0;
  69. while(!Q.empty())
  70. {
  71. node*x = Q.front();
  72. Q.pop();
  73. //cout<<"("<<x->x<<","<<x->y<<")"<<endl;
  74. if(x->x == endi && x->y == endj)
  75. {
  76. flag=1;
  77. break;
  78. }
  79.  
  80. visited[x->x][x->y]=1;
  81.  
  82. for(long long i=0;i<4;i++)
  83. {
  84. long long X = x->x + rows[i];
  85. long long Y = x->y + cols[i];
  86. char direction = d[i];
  87.  
  88. if(isValid(X,Y,n,m) && visited[X][Y] == 0 && (mat[X][Y] != '#'))
  89. {
  90. Q.push(new node(X,Y));
  91. dir[X][Y] = direction;
  92. }
  93. }
  94. }
  95.  
  96.  
  97. if(flag == 0)
  98. {
  99. cout<<"NO"<<endl;
  100. }
  101. else
  102. {
  103. long long i=endi;
  104. long long j=endj;
  105.  
  106. string S="";
  107. while(!(i==starti && j==startj))
  108. {
  109. //cout<<"i="<<i<<" j="<<j<<endl;
  110. if(dir[i][j] == 'U')
  111. {
  112. i++;
  113. S+='U';
  114. }
  115. else if(dir[i][j] == 'D')
  116. {
  117. i--;
  118. S+='D';
  119. }
  120. else if(dir[i][j] == 'L')
  121. {
  122. j++;
  123. S+='L';
  124. }
  125. else if(dir[i][j] == 'R')
  126. {
  127. j--;
  128. S+='R';
  129. }
  130. //cout<<"i="<<i<<" j="<<j<<endl;
  131. }
  132.  
  133.  
  134.  
  135. reverse(S.begin(),S.end());
  136.  
  137. cout<<"YES"<<endl;
  138. cout<<S.length()<<endl;
  139. cout<<S<<endl;
  140.  
  141. }
  142.  
  143.  
  144.  
  145. return 0;
  146. }
Success #stdin #stdout 0.01s 5288KB
stdin
10 10
...#..A.#.
....B...##
...#......
..........
...#.#....
..##..#...
.......#..
#.......#.
...#....#.
#......#..
stdout
YES
3
LLD