fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false; 
  15. }
  16.  
  17. const int N = 15e2 + 5; 
  18.  
  19. // i = 0: chéo lên bên trái
  20. // i = 1: chéo lên bên phải
  21. // i = 2: chéo xuống bên trái
  22. // i = 3: chéo xuống bên phải
  23. int dx[4] = {-1, -1, 1, 1}; 
  24. int dy[4] = {-1, 1, -1, 1};  
  25.  
  26. int n; 
  27. int sx, sy, tx, ty; 
  28. string board[N]; 
  29.  
  30. bool ok(int x, int y) {
  31. 	return (0 <= x && x < n && 0 <= y && y < n && board[x][y] == '.');  
  32. }
  33.  
  34. struct Node {
  35. 	int x, y, i; 
  36. }; 
  37.  
  38. int dist[N][N][5]; // dist[x][y][i] = Số bước ít nhất để quân tượng từ ô (sx, sy) đến được ô (x, y) 
  39. 				   //				  và đang đi theo hướng i
  40.  
  41. int bfs(int sx, int sy, int tx, int ty) {
  42. 	for (int x = 0; x < n; x++) {
  43. 		for (int y = 0; y < n; y++) {
  44. 			for (int i = 0; i <= 4; i++) dist[x][y][i] = INF;  
  45. 		}
  46. 	}
  47.  
  48. 	deque<Node> dq; 
  49. 	dist[sx][sy][4] = 0;  
  50. 	dq.push_back({sx, sy, 4});  
  51.  
  52. 	while (!dq.empty()) {
  53. 		Node front = dq.front(); dq.pop_front();  
  54. 		int x = front.x, y = front.y, i = front.i;  
  55.  
  56. 		if (x == tx && y == ty) return dist[x][y][i]; 
  57.  
  58. 		for (int nxt_i = 0; nxt_i < 4; nxt_i++) {
  59. 			int nxt_x = x + dx[nxt_i]; 
  60. 			int nxt_y = y + dy[nxt_i]; 
  61. 			int w = (i == nxt_i) ? 0 : 1; 
  62.  
  63. 			if (!ok(nxt_x, nxt_y)) continue;   
  64.  
  65. 			if (minimize(dist[nxt_x][nxt_y][nxt_i], dist[x][y][i] + w)) {
  66. 				if (w == 0) {
  67. 					dq.push_front({nxt_x, nxt_y, nxt_i});  
  68. 				}
  69. 				else {
  70. 					dq.push_back({nxt_x, nxt_y, nxt_i}); 
  71. 				}
  72. 			}
  73. 		}
  74. 	}
  75.  
  76. 	return -1; 
  77. }
  78.  
  79. int main() {
  80. 	ios::sync_with_stdio(false); 
  81. 	cin.tie(nullptr); 	
  82. 	cin >> n; 
  83. 	cin >> sx >> sy; 
  84. 	cin >> tx >> ty;  
  85. 	--sx, --sy;  
  86. 	--tx, --ty; 
  87. 	for (int i = 0; i < n; i++) {
  88. 		cin >> board[i]; 
  89. 	} 
  90.  
  91. 	int ans = bfs(sx, sy, tx, ty); 
  92.  
  93. 	cout << ans << '\n'; 
  94. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
1 3
3 5
....#
...#.
.....
.#...
#....
stdout
copy 
3
https://ideone.com/Lj4jPT
language:
C++14 (gcc 8.3)
created:
277 days ago
visibility:
secret

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!