fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10. 	int x,y;
  11. 	node(int x1,int y1)
  12. 	{
  13. 		x=x1;
  14. 		y=y1;
  15. 	}
  16. };
  17.  
  18. struct node2
  19. {
  20. 	int x,y;
  21. 	char d;
  22. 	node2(int x1,int y1,char d1)
  23. 	{
  24. 		x=x1;
  25. 		y=y1;
  26. 		d=d1;
  27. 	}
  28. };
  29.  
  30. node2* prev1[1001][1001];
  31. int rows[]={0,1,0,-1};
  32. int cols[]={1,0,-1,0};
  33. char dir[]={'R','D','L','U'};
  34. int startPlayeri=-1;
  35. int startPlayerj=-1;
  36. vector<node*> monsterLocations;
  37. int monsterTime[1001][1001];
  38. int playerTime[1001][1001];
  39. int possible=0;
  40. int visited[1001][1001];
  41.  
  42. bool isValid(int x,int y,int n,int m)
  43. {
  44. 	return x>=0 && y>=0 && x<n && y<m;
  45. }
  46.  
  47. bool isEdge(int x,int y,int n,int m)
  48. {
  49. 	return (x==0) || (y==0) || (x==(n-1)) || (y==(m-1));
  50. }
  51.  
  52. void constructPath(int x,int y)
  53. {
  54. 	cout<<"YES"<<endl;
  55. 	node2* val = prev1[x][y];
  56. 	string result = "";
  57. 	while(val->x != -1)
  58. 	{
  59. 		//cout<<"x="<<val->x<<" y="<<val->y<<" d="<<val->d<<endl;
  60. 		result+=val->d;
  61. 		val = prev1[val->x][val->y];
  62. 	}
  63. 	reverse(result.begin(),result.end());
  64. 	cout<<result.length()<<endl;
  65. 	cout<<result<<endl;
  66. 	return;
  67. }
  68.  
  69.  
  70. int main() {
  71.  
  72. 	int n,m;
  73. 	cin>>n>>m;
  74.  
  75. 	vector<string> grid;
  76. 	for(int i=0;i<n;i++)
  77. 	{
  78. 		string x;
  79. 		cin>>x;
  80. 		grid.push_back(x);
  81. 	}
  82.  
  83.  
  84. 	for(int i=0;i<n;i++)
  85. 	{
  86. 		for(int j=0;j<m;j++)
  87. 		{
  88. 			monsterTime[i][j]=INT_MAX;
  89. 			playerTime[i][j]=INT_MAX;
  90. 			visited[i][j]=0;
  91. 			if(grid[i][j] == 'A')
  92. 			{
  93. 				startPlayeri = i;
  94. 				startPlayerj = j;
  95. 				playerTime[i][j]=0;
  96. 			}
  97.  
  98. 			if(grid[i][j] == 'M')
  99. 			{
  100. 				monsterLocations.push_back(new node(i,j));
  101. 				monsterTime[i][j]=0;
  102. 			}
  103. 		}
  104. 	}
  105.  
  106. 	queue<node*> Q;
  107. 	for(int i=0;i<monsterLocations.size();i++)
  108. 	{
  109. 		Q.push(monsterLocations[i]);
  110. 	}
  111.  
  112. 	while(!Q.empty())
  113. 	{
  114. 		node*x = Q.front();
  115. 		Q.pop();
  116. 		int newTime = monsterTime[x->x][x->y]+1;
  117. 		for(int i=0;i<4;i++)
  118. 		{
  119. 			int X = x->x + rows[i];
  120. 			int Y = x->y + cols[i];
  121. 			char direction = dir[i];
  122.  
  123. 			if(isValid(X,Y,n,m) && grid[X][Y] != '#' && monsterTime[X][Y] > newTime)
  124. 			{
  125. 				Q.push(new node(X,Y));
  126. 				monsterTime[X][Y] = newTime;
  127. 			}
  128. 		}
  129. 	}
  130.  
  131. 	queue<node2*> Q2;
  132. 	Q2.push(new node2(startPlayeri,startPlayerj,'*'));
  133. 	prev1[startPlayeri][startPlayerj] = new node2(-1,-1,'*');
  134. 	while(!Q2.empty())
  135. 	{
  136. 		node2*x = Q2.front();
  137. 		Q2.pop();
  138.  
  139. 		visited[x->x][x->y]=1;
  140. 		//cout<<"x="<<x->x<<" y="<<x->y<<" isEdge="<<isEdge(x->x,x->y,n,m)<<endl;
  141.  
  142. 		if(isEdge(x->x,x->y,n,m))
  143. 		{
  144. 			possible=1;
  145. 			constructPath(x->x,x->y);
  146. 			return 0;
  147. 		}
  148.  
  149. 		int newTime = playerTime[x->x][x->y]+1;
  150. 		//cout<<"newTime="<<newTime<<endl;
  151. 		for(int i=0;i<4;i++)
  152. 		{
  153. 			int X = x->x + rows[i];
  154. 			int Y = x->y + cols[i];
  155. 			char direction = dir[i];
  156.  
  157. 			if(isValid(X,Y,n,m) && grid[X][Y] != '#' && visited[X][Y]==0 && monsterTime[X][Y] > newTime)
  158. 			{
  159. 				visited[X][Y]=1;
  160. 				node2* nod = new node2(X,Y,direction);
  161. 				Q2.push(nod);
  162. 				playerTime[X][Y] = newTime;
  163. 				prev1[X][Y] = new node2(x->x,x->y,direction);
  164. 			}
  165. 		}
  166.  
  167. 	}
  168.  
  169. 	if(possible == 0)
  170. 	{
  171. 		cout<<"NO"<<endl;
  172. 	}
  173.  
  174.  
  175. 	return 0;
  176. }
Success #stdin #stdout 0.01s 9716KB
comments (?)
stdin
copy 
8 8
########
#.....A#
#.######
#......#
#.####.#
#....#.#
#.##.#.#
#.#M.#.#
stdout
copy 
YES
16
LLLLLDDRRRRRDDDD
https://ideone.com/7pGD5R
language:
C++14 (gcc 8.3)
created:
4 days 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!