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. void minimize(T& a, const T& b) {
  13. 	if (b < a) a = b; 
  14. }
  15.  
  16. template<typename T>
  17. void maximize(T& a, const T& b) {
  18. 	if (a < b) a = b;  
  19. }
  20.  
  21. const int N = 1e2 + 5; 
  22.  
  23. int dx[2][8] = {{0, 0, -1, 1, -1, -1, 1, 1}, 
  24. 				{-1, -1, -2, -2, 1, 1, 2, 2}}; 
  25.  
  26. int dy[2][8] = {{-1, 1, 0, 0, -1, 1, -1, 1}, 
  27. 				{-2, 2, -1, 1, -2, 2, -1, 1}};
  28.  
  29. int n; 
  30. string board[N]; 
  31. int kx, ky;  
  32. vector<ii> knights; 
  33.  
  34. bool ok(int x, int y) {
  35. 	return (1 <= x && x <= n && 1 <= y && y <= n && board[x][y] != '#');
  36. }
  37.  
  38. struct Node {
  39. 	int x, y, parity; 
  40. }; 
  41.  
  42. int dist[N][N][2];
  43. int mx[N][N][2];
  44.  
  45. void bfs(int sx, int sy, int type) {
  46. 	for (int x = 1; x <= n; x++) {
  47. 		for (int y = 1; y <= n; y++) {
  48. 			dist[x][y][0] = dist[x][y][1] = INF;
  49. 		}
  50. 	}
  51. 	queue<Node> q;
  52. 	dist[sx][sy][0] = 0;  
  53. 	q.push({sx, sy, 0}); 
  54.  
  55. 	while (!q.empty()) {
  56. 		auto [x, y, parity] = q.front(); q.pop();  
  57. 		for (int i = 0; i < 8; i++) {
  58. 			int nx = x + dx[type][i], ny = y + dy[type][i]; 
  59. 			int nparity = parity ^ 1; 
  60. 			if (!ok(nx, ny)) continue;
  61. 			if (dist[nx][ny][nparity] == INF) {
  62. 				dist[nx][ny][nparity] = dist[x][y][parity] + 1; 
  63. 				q.push({nx, ny, nparity});
  64. 			}
  65. 		}
  66. 	}
  67.  
  68. 	for (int x = 1; x <= n; x++) {
  69. 		for (int y = 1; y <= n; y++) {
  70. 			for (int parity = 0; parity <= 1; parity++) {
  71. 				maximize(mx[x][y][parity], dist[x][y][parity]);
  72. 			}
  73. 		}
  74. 	}
  75. }
  76.  
  77. int main() {
  78. 	ios::sync_with_stdio(false); 
  79. 	cin.tie(nullptr); 	
  80. 	cin >> n; 
  81. 	for (int x = 1; x <= n; x++) {
  82. 		cin >> board[x];
  83. 		board[x] = ' ' + board[x]; 
  84. 		for (int y = 1; y <= n; y++) {
  85. 			if (board[x][y] == 'T') {kx = x; ky = y;}
  86. 			if (board[x][y] == 'M') knights.push_back({x, y});  	 
  87. 		}
  88. 	}
  89.  
  90. 	bfs(kx, ky, 0);  
  91. 	for (auto [sx, sy] : knights) bfs(sx, sy, 1); 
  92.  
  93. 	int ans = INF;  
  94. 	for (int x = 1; x <= n; x++) {
  95. 		for (int y = 1; y <= n; y++) {
  96. 			for (int parity = 0; parity <= 1; parity++) {
  97. 				minimize(ans, mx[x][y][parity]);
  98. 			}
  99. 		}
  100. 	}	
  101. 	if (ans == INF) ans = -1; 
  102. 	cout << ans << '\n';
  103. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
M....
.....
.#...
.#..#
...#T
stdout
copy 
2
https://ideone.com/j0Xy30
language:
C++14 (gcc 8.3)
created:
8 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!