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 = 2e9;  
  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. int dx[4] = {0, 0, -1, 1}; 
  18. int dy[4] = {-1, 1, 0, 0};  
  19.  
  20. const int N = 2e3 + 5; 
  21.  
  22. int n, m; 
  23. int sx, sy; 
  24. int a, b;  
  25. string s[N];  
  26.  
  27. bool ok(int x, int y) {
  28. 	return (0 <= x && x < n && 0 <= y && y < m && s[x][y] == '.'); 
  29. }
  30.  
  31. // sy + cnt_right - cnt_left = y
  32. // (sy - y) + cnt_right = cnt_left 
  33. //   const  + cnt_right = cnt_left
  34. // => Chỉ cần tối ưu cnt_right hoặc cnt_left thì thằng còn lại cũng sẽ tối ưu theo
  35.  
  36. int dist[N][N]; // dist[x][y] = Số bước đi sang phải (cnt_right) ít nhất
  37. 				//              để từ ô (sx, sy) đến được ô (x, y)
  38.  
  39. void bfs(int sx, int sy) {
  40. 	for (int x = 0; x < n; x++) {
  41. 		for (int y = 0; y < m; y++) dist[x][y] = INF;  
  42. 	}
  43.  
  44. 	deque<ii> dq;  
  45. 	dist[sx][sy] = 0;   
  46. 	dq.push_back({sx, sy});  
  47.  
  48. 	while (!dq.empty()) {
  49. 		ii front = dq.front(); dq.pop_front();  
  50. 		int x = front.first, y = front.second;  
  51.  
  52. 		for (int i = 0; i < 4; i++) {
  53. 			int nx = x + dx[i], ny = y + dy[i]; 
  54. 			int w = (i == 1) ? 1 : 0;   
  55.  
  56. 			if (!ok(nx, ny)) continue; 
  57.  
  58. 			if (minimize(dist[nx][ny], dist[x][y] + w)) {
  59. 				if (w == 0) {
  60. 					dq.push_front({nx, ny});  
  61. 				}
  62. 				else {
  63. 					dq.push_back({nx, ny}); 
  64. 				}
  65. 			}
  66. 		}
  67. 	}
  68. }
  69.  
  70. int cnt[N][N];  
  71.  
  72. int main() {
  73. 	ios::sync_with_stdio(false); 
  74. 	cin.tie(nullptr); 	
  75. 	cin >> n >> m; 
  76. 	cin >> sx >> sy;  
  77. 	--sx, --sy;  
  78. 	cin >> a >> b;  
  79.  
  80. 	for (int x = 0; x < n; x++) cin >> s[x]; 
  81.  
  82. 	bfs(sx, sy);  
  83.  
  84. 	int ans = 0;  
  85. 	for (int x = 0; x < n; x++) {
  86. 		for (int y = 0; y < m; y++) {
  87. 			if (dist[x][y] == INF) continue; 
  88. 			int cnt_right = dist[x][y];   
  89. 			int cnt_left = (sy - y) + cnt_right;  
  90. 			ans += (cnt_left <= a && cnt_right <= b);  
  91. 		}
  92. 	}
  93.  
  94. 	cout << ans << '\n'; 
  95. }
Success #stdin #stdout 0.01s 5804KB
comments (?)
stdin
copy 
4 5
3 2
1 2
.....
.***.
...**
*....
stdout
copy 
10
https://ideone.com/SwZS9v
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!