fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e3 + 5; 
  12.  
  13. int dx[4] = {0, 0, -1, 1}; 
  14. int dy[4] = {-1, 1, 0, 0};  
  15. char dir[4] = {'L', 'R', 'U', 'D'};
  16.  
  17. int n, m; 
  18. string s[N]; 
  19.  
  20. bool ok(int x, int y) {
  21. 	return (0 <= x && x < n && 0 <= y && y < m && s[x][y] != '#'); 
  22. }
  23.  
  24. bool vis[N][N];  
  25. int p[N][N];
  26.  
  27. void bfs(int sx, int sy) {
  28. 	for (int x = 0; x < n; x++) {
  29. 		for (int y = 0; y < m; y++) {
  30. 			vis[x][y] = false; 
  31. 			p[x][y] = -1;  
  32. 		}
  33. 	}
  34.  
  35. 	queue<ii> q;  
  36. 	vis[sx][sy] = true;  
  37. 	q.push({sx, sy});  
  38.  
  39. 	while (!q.empty()) {
  40. 		ii u = q.front(); q.pop(); 
  41. 		int x = u.first, y = u.second; 
  42.  
  43. 		for (int i = 0; i < 4; i++) {
  44. 			int nx = x + dx[i], ny = y + dy[i]; 
  45. 			if (ok(nx, ny) && !vis[nx][ny]) {
  46. 				vis[nx][ny] = true; 
  47. 				p[nx][ny] = i;  
  48. 				q.push({nx, ny}); 
  49. 			}
  50. 		}
  51. 	}
  52. }
  53.  
  54. int main() {
  55. 	ios::sync_with_stdio(false); 
  56. 	cin.tie(nullptr); 	
  57. 	cin >> n >> m; 
  58.  
  59. 	int sx = -1, sy = -1, tx = -1, ty = -1;   
  60. 	for (int i = 0; i < n; i++) {
  61. 		cin >> s[i]; 
  62. 		for (int j = 0; j < m; j++) {
  63. 			if (s[i][j] == 'A') {sx = i, sy = j;}
  64. 			if (s[i][j] == 'B') {tx = i, ty = j;}
  65. 		}
  66. 	}
  67.  
  68. 	bfs(sx, sy); 
  69.  
  70. 	if (!vis[tx][ty]) {
  71. 		cout << "NO" << '\n'; 
  72. 		return 0; 
  73. 	}
  74.  
  75. 	cout << "YES" << '\n'; 
  76.  
  77. 	string path = "";   
  78. 	while (true) {
  79. 		if (tx == sx && ty == sy) break;  
  80. 		int i = p[tx][ty];  
  81. 		path += dir[i]; 
  82. 		tx -= dx[i], ty -= dy[i]; 
  83. 	}
  84.  
  85. 	reverse(path.begin(), path.end());  
  86.  
  87. 	cout << path.size() << '\n'; 
  88. 	cout << path << '\n'; 
  89. }
Success #stdin #stdout 0.01s 5684KB
comments (?)
stdin
copy 
5 8
########
#.A#...#
#.##.#B#
#......#
########
stdout
copy 
YES
9
LDDRRRRRU
https://ideone.com/w60IZz
language:
C++14 (gcc 8.3)
created:
291 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!