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