fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int n,m;
  5.  
  6. string ans;
  7. //priority_queue< string, vector<string>, greater<string>> ans;
  8. unordered_map<char,pair<int,int>>graph;
  9.  
  10.  
  11. bool valid(int a, int b)
  12. {
  13. 	if(a<0||b<0||a>=n||b>=m)return false;
  14. 	return true;
  15. }
  16.  
  17. string path(int a2,int b2,int a1,int b1,vector<vector<char>>&steps)
  18. {
  19. 	if(a1==a2&&b1==b2)return ans;
  20.  
  21. 	auto temp=graph[steps[a2][b2]];
  22.  
  23. 	ans+=steps[a2][b2];
  24.  
  25. 	path(a2-temp.first,b2-temp.second,a1,b1,steps);
  26.  
  27. 	return ans;
  28. }
  29.  
  30. int main() {
  31.  
  32. 	cin>>n>>m;
  33. 	int flag=0;
  34. 	int a,b;
  35.  
  36. 	vector<vector<char>>arr(n,vector<char>(m));
  37. 	vector<vector<char>>steps(n,vector<char>(m));
  38.  
  39. 	for(int i=0;i<n;i++)
  40. 	{
  41. 		for(int j=0;j<m;j++)
  42. 		{
  43. 			cin>>arr[i][j];
  44. 			if(arr[i][j]=='A')a=i,b=j;
  45. 		}
  46. 	}
  47.  
  48.  
  49. 	arr[a][b]='.';
  50.  
  51.  
  52. 	deque <pair<int,int>> Q;
  53.  
  54. 	Q.push_back({a,b});
  55.  
  56. 	vector<pair<pair<int,int>, char>> dir
  57. 	{
  58. 		{{-1,0},'U'}, {{0,1},'R'}, {{0,-1},'L'}, {{1,0},'D'}
  59. 	};
  60.  
  61. 	for(auto x: dir)
  62. 	{
  63. 		graph[x.second]=x.first;
  64. 	}
  65.  
  66.  
  67. 	while(Q.size())
  68. 	{
  69. 		int a1=Q.front().first;
  70. 		int b1=Q.front().second;
  71.  
  72. 		Q.pop_front();
  73.  
  74. 	//	cout<<a1<<b1<<arr[a1][b1]<<endl;
  75.  
  76. 		if(arr[a1][b1]=='B')
  77. 		{
  78. 			string ok=path(a1,b1,a,b,steps);
  79. 			reverse(ok.begin(),ok.end());
  80. 			cout<<"YES"<<endl<<ok.size()<<endl<<ok;
  81. 			flag=1; 
  82. 			break;
  83. 		}
  84.  
  85. 		else 	
  86. 		arr[a1][b1]='#';
  87.  
  88. 		for(auto x : dir)
  89. 		{
  90. 			int a2=x.first.first + a1;
  91. 			int b2=x.first.second + b1;
  92. 			int d=x.second;
  93.  
  94. 		//	cout<<a2<<b2<<arr[a2][b2]<<endl;
  95.  
  96. 			if(valid(a2,b2) and arr[a2][b2]!='#')
  97. 			{
  98. 				Q.push_back({a2,b2});
  99. 				if(arr[a2][b2]!='B')
  100. 				arr[a2][b2] ='#';
  101. 				steps[a2][b2]=d;
  102. 			}
  103.  
  104. 		}
  105.  
  106.  
  107.  
  108. 	}
  109.  
  110.  
  111. 	if(!flag)cout<<"NO";
  112.  
  113.  
  114. }
  115.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 8
########
#.A#...#
#.##.#B#
#......#
########
stdout
copy 
YES
9
LDDRRRRRU
https://ideone.com/f7MeY1
language:
C++14 (gcc 8.3)
created:
8 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!