fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 5001;
  4. char path[MAX][MAX];
  5. vector<vector<int> > valid(MAX,vector<int>(MAX,0));
  6. int dx[] = {0,0,-1,1};
  7. int dy[] = {-1,1,0,0};
  8. string moves[] = {"L","R","U","D"};
  9. int n,m;
  10.  
  11. bool is_sol(pair<int,int> point){
  12. 	return point.first == 0 || point.first == n-1 
  13. 	 ||   point.second == 0 || point.second == m-1; 
  14. }
  15.  
  16. bool check(pair<int,int> p){
  17. 	if(p.first<0 || p.second<0 || !valid[p.first][p.second] ||
  18. 	p.first>=n || p.second>=m || path[p.first][p.second]!='.')  return false;
  19. 	return true;
  20. }
  21.  
  22. int main(){
  23.  
  24. 	ios_base::sync_with_stdio(false);
  25. 	cin.tie(0); cout.tie(0);
  26.  
  27. 	queue<pair<int,int> > pq_; //this is for monsters..
  28. 	queue<pair<pair<int,int>,string> > pq; // this is for the player...
  29.  
  30. 	cin>>n>>m;
  31. 	for(int i = 0;i<n;i++)
  32. 		for(int j = 0;j<m;j++){ 
  33. 			cin>>path[i][j];
  34. 			if(path[i][j]=='.') valid[i][j] = 1;
  35. 			else if(path[i][j] == 'A') pq.push({{i,j},""});	
  36. 			else if(path[i][j] == 'M') pq_.push({i,j});
  37. 		}
  38.  
  39.  
  40. 	while(!pq.empty()){
  41.  
  42. 		pair<int,int> p = pq_.front();
  43. 		pq_.pop();
  44.  
  45. 		for(int i = 0;i<4;i++){
  46.  
  47. 			int xx_ = p.first + dx[i];
  48. 			int yy_ = p.second + dy[i];
  49. 			if(check(make_pair(xx_,yy_)))
  50. 			{ 
  51. 				pq_.push({xx_,yy_}); valid[xx_][yy_] = 0; 
  52.  
  53. 			}
  54. 		 }
  55.  
  56. 		pair<pair<int,int>,string> q = pq.front();
  57. 		pq.pop();
  58.  
  59. 		string s = q.second; 
  60. 		if(is_sol({q.first.first,q.first.second})){
  61. 			cout<<"YES"<<'\n'<<s.length()<<'\n';
  62. 			cout<<s<<'\n';
  63. 			return 0; 
  64. 		}
  65.  
  66.  
  67. 		 	for(int i = 0;i<4;i++){
  68.  
  69. 			int xx_ = q.first.first + dx[i];
  70. 			int yy_ = q.first.second + dy[i];
  71. 			if(check(make_pair(xx_,yy_)))
  72. 			{ 
  73. 				pq.push({{xx_,yy_},s + moves[i]}); valid[xx_][yy_] = 0; 
  74.  
  75. 			}
  76. 		 }
  77. 	}
  78.  
  79. 	cout<<"NO"<<'\n';	
  80.  
  81. 	return 0;	
  82. }
  83.  
Success #stdin #stdout 0.03s 101408KB
comments (?)
stdin 
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
stdout 
YES
5
RRDDR
https://ideone.com/sRtFZ3
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!