Advertisement
Josif_tepe

Untitled

Nov 6th, 2022
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. char mat[1111][1111];
  7. bool visited[1111][1111];
  8. int prev_steps[1111][1111];
  9. int main() {
  10. ios_base::sync_with_stdio(false);
  11.  
  12. int n, m;
  13. cin >> n >> m;
  14. int si, sj, ei, ej;
  15. for(int i = 0; i < n; i++) {
  16. for(int j = 0; j < m; j++) {
  17. cin >> mat[i][j];
  18. visited[i][j] = false;
  19. if(mat[i][j] == 'A') {
  20. si = i; sj = j;
  21. }
  22. if(mat[i][j] == 'B') {
  23. ei = i; ej = j;
  24. }
  25. }
  26. }
  27. int di[] = {1, -1, 0, 0};
  28. int dj[] = {0, 0, 1, -1};
  29. queue<int> Q;
  30. Q.push(si); Q.push(sj); Q.push(0);
  31. visited[si][sj] = true;
  32. int dist = -1;
  33. while(!Q.empty()) {
  34. int ci = Q.front(); Q.pop();
  35. int cj = Q.front(); Q.pop();
  36. int cekor = Q.front(); Q.pop();
  37.  
  38. if(ci == ei and cj == ej) {
  39. dist = cekor;
  40. break;
  41. }
  42. for(int i = 0; i < 4; i++) {
  43. int ti = ci + di[i];
  44. int tj = cj + dj[i];
  45. if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
  46. Q.push(ti);
  47. Q.push(tj);
  48. Q.push(cekor + 1);
  49. visited[ti][tj] = true;
  50. prev_steps[ti][tj] = i;
  51. }
  52. }
  53. }
  54. if(dist == -1) {
  55. cout << "NO" << endl;
  56. return 0;
  57. }
  58. cout << "YES" << endl << dist << endl;
  59. pair<int, int> S = make_pair(si, sj), E = make_pair(ei, ej);
  60. string result = "";
  61. while(E != S) {
  62. int dir = prev_steps[E.first][E.second];
  63. if(dir == 0) {
  64. result += "D";
  65. }
  66. else if(dir == 1) {
  67. result += "U";
  68. }
  69. else if(dir == 2) {
  70. result += "R";
  71. }
  72. else {
  73. result += "L";
  74. }
  75. E = make_pair(E.first - di[dir], E.second - dj[dir]);
  76. }
  77. reverse(result.begin(), result.end());
  78. cout << result << endl;
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement