fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<string> mat;
  7. char dir[1001][1001];
  8. long long visited[1001][1001];
  9.  
  10. struct node
  11. {
  12. 	long long x,y;
  13. 	node(long long x1,long long y1)
  14. 	{
  15. 		x=x1;
  16. 		y=y1;
  17. 	}
  18. };
  19.  
  20. long long rows[]={0,1,0,-1};
  21. long long cols[]={1,0,-1,0};
  22. char d[] = {'R','D','L','U'};
  23.  
  24. bool isValid(long long x,long long y,long long n,long long m)
  25. {
  26. 	return x>=0 && y>=0 && x<n && y<m;
  27. }
  28.  
  29. int main() {
  30.  
  31. 	long long n,m;
  32. 	cin>>n>>m;
  33.  
  34. 	long long starti,startj,endi,endj;
  35.  
  36. 	for(long long i=0;i<n;i++)
  37. 	{
  38. 		string x;
  39. 		cin>>x;
  40. 		mat.push_back(x);
  41. 	}
  42.  
  43. 	for(long long i=0;i<n;i++)
  44. 	{
  45. 		//cout<<mat[i]<<endl;
  46. 		for(long long j=0;j<m;j++)
  47. 		{
  48. 			if(mat[i][j] == 'A')
  49. 			{
  50. 				starti=i;
  51. 				startj=j;
  52. 			}
  53. 			if(mat[i][j] == 'B')
  54. 			{
  55. 				endi=i;
  56. 				endj=j;
  57. 			}
  58. 			dir[i][j] = 'X';
  59. 			visited[i][j] = 0;
  60. 		}
  61. 	}
  62.  
  63. 	queue<node*> Q;
  64. 	Q.push(new node(starti,startj));
  65.  
  66. 	//cout<<"starti="<<starti<<" startj="<<startj<<endl;
  67. 	//cout<<"endi="<<endi<<" endj="<<endj<<endl;
  68. 	long long flag=0;
  69. 	while(!Q.empty())
  70. 	{
  71. 		node*x = Q.front();
  72. 		Q.pop();
  73. 		//cout<<"("<<x->x<<","<<x->y<<")"<<endl;
  74. 		if(x->x == endi && x->y == endj)
  75. 		{
  76. 			flag=1;
  77. 			break;
  78. 		}
  79.  
  80. 		visited[x->x][x->y]=1;
  81.  
  82. 		for(long long i=0;i<4;i++)
  83. 		{
  84. 			long long X = x->x + rows[i];
  85. 			long long Y = x->y + cols[i];
  86. 			char direction = d[i];
  87.  
  88. 			if(isValid(X,Y,n,m) && visited[X][Y] == 0 && (mat[X][Y] != '#'))
  89. 			{
  90. 				Q.push(new node(X,Y));
  91. 				dir[X][Y] = direction; 
  92. 			}
  93. 		}
  94. 	}
  95.  
  96.  
  97. 	if(flag == 0)
  98. 	{
  99. 		cout<<"NO"<<endl;
  100. 	}
  101. 	else
  102. 	{
  103. 		long long i=endi;
  104. 		long long j=endj;
  105.  
  106. 		string S="";
  107. 		while(!(i==starti && j==startj))
  108. 		{
  109. 			//cout<<"i="<<i<<" j="<<j<<endl;
  110. 			if(dir[i][j] == 'U')
  111. 			{
  112. 				i++;
  113. 				S+='U';
  114. 			}
  115. 			else if(dir[i][j] == 'D')
  116. 			{
  117. 				i--;
  118. 				S+='D';
  119. 			}
  120. 			else if(dir[i][j] == 'L')
  121. 			{
  122. 				j++;
  123. 				S+='L';
  124. 			}
  125. 			else if(dir[i][j] == 'R')
  126. 			{
  127. 				j--;
  128. 				S+='R';
  129. 			}
  130. 			//cout<<"i="<<i<<" j="<<j<<endl;
  131. 		}
  132.  
  133.  
  134.  
  135. 		reverse(S.begin(),S.end());
  136.  
  137. 		cout<<"YES"<<endl;
  138. 		cout<<S.length()<<endl;
  139. 		cout<<S<<endl;
  140.  
  141. 	}
  142.  
  143.  
  144.  
  145. 	return 0;
  146. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10 10
...#..A.#.
....B...##
...#......
..........
...#.#....
..##..#...
.......#..
#.......#.
...#....#.
#......#..
stdout
copy 
YES
3
LLD
https://ideone.com/2RP2BT
language:
C++14 (gcc 8.3)
created:
11 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!