fork download 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. struct Bird{
  6. 	int y, x;
  7. };
  8.  
  9. struct Compare{
  10.     bool operator()(pair<int, Bird> p1, pair<int, Bird> p2) {
  11.         return p1.first < p2.first;
  12.     }
  13. };
  14.  
  15. pair<int, int> dir[4] = {
  16. 	make_pair(-1, 0), make_pair(1, 0), make_pair(0, -1), make_pair(0, 1)
  17. };
  18. int id = 1;
  19. int R, C;
  20. pair<int, int> dest;
  21. int answer = -1;
  22. char map[1500][1500] = {0,};
  23. bool visited[1500][1500] = {false, };
  24. int melted[1500][1500] = {false, };
  25. int cache[1500][1500] = {false, };
  26. priority_queue<pair<int, Bird>, vector<pair<int, Bird>>, Compare> bq; 
  27.  
  28. void input(){
  29. 	cin>>R>>C;
  30.  
  31. 	for(int i=0;i<R;i++){
  32. 		for(int j=0;j<C;j++){
  33. 			cin>>map[i][j];
  34.  
  35. 			if(map[i][j]!='X') melted[i][j] = true;
  36. 			if(map[i][j]=='L'){
  37. 				if(id==1){
  38. 					Bird b;
  39. 					b.y=i;
  40. 					b.x=j;
  41. 					id=-1;
  42. 					bq.push(make_pair(0, b));
  43. 					visited[b.y][b.x]=true;
  44. 				}else{
  45. 					dest=make_pair(i, j);
  46. 				}
  47. 			}
  48. 		}
  49. 	}
  50. }
  51.  
  52. void melting(){
  53. 	queue<pair<int, int>> q;
  54.  
  55. 	for(int y=0;y<R;y++){
  56. 		for(int x=0;x<C;x++){
  57. 			if(map[y][x]=='X') continue;
  58. 			for(int i=0;i<4;i++){
  59. 				int ny = y+dir[i].first;
  60. 				int nx = x+dir[i].second;
  61.  
  62. 				if(melted[ny][nx]) continue;
  63. 				if(ny<0||ny>=R||nx<0||nx>=C) continue;
  64. 				if(map[ny][nx]=='X'){
  65. 					melted[ny][nx] = true;
  66. 					cache[ny][nx] = cache[y][x] + 1;
  67. 					q.push(make_pair(ny, nx));
  68. 				} 
  69. 			}
  70. 		}
  71. 	}
  72.  
  73. 	while(!q.empty()){
  74. 		int y = q.front().first;
  75. 		int x = q.front().second;
  76. 		q.pop();
  77.  
  78. 		for(int i=0;i<4;i++){
  79. 			int ny = y+dir[i].first;
  80. 			int nx = x+dir[i].second;
  81. 			if(ny<0||ny>=R||nx<0||nx>=C) continue;
  82. 			if(!melted[ny][nx]){
  83. 				melted[ny][nx] = true;
  84. 				cache[ny][nx] = cache[y][x] + 1;
  85. 				q.push(make_pair(ny, nx));
  86. 			}
  87. 		}
  88. 	}
  89. }
  90.  
  91. void moveTheBirds(){
  92. 	while(!bq.empty()){
  93. 		Bird b = bq.top().second;
  94. 		answer = max(-bq.top().first, answer);
  95. 		bq.pop();
  96. 		// cout<<b.y<<" "<<b.x<<'\n';
  97. 		if(b.y==dest.first && b.x==dest.second){
  98. 			cout<<answer<<'\n';
  99. 			return;
  100. 		}
  101.  
  102. 		for(int i=0;i<4;i++){
  103. 			int ny = b.y+dir[i].first;
  104. 			int nx = b.x+dir[i].second;
  105. 			if(ny<0||ny>=R||nx<0||nx>=C) continue;
  106. 			if(visited[ny][nx]) continue;
  107. 			visited[ny][nx] = true;
  108. 			Bird nb;
  109. 			nb.y=ny;
  110. 			nb.x=nx;
  111. 			bq.push(make_pair(-cache[ny][nx], nb));
  112. 		}
  113. 	}
  114. }
  115.  
  116. int main() {
  117. 	cin.tie(0);
  118. 	cout.tie(0);
  119. 	ios::sync_with_stdio(0);
  120.  
  121. 	input();
  122. 	melting();
  123. 	moveTheBirds();
  124.  
  125. 	return 0;
  126. }
Success #stdin #stdout 0.01s 9764KB
comments (?)
stdin 
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...
stdout 
2
https://ideone.com/t1pe00
language:
C++ (gcc 8.3)
created:
15 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!