fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int mxN = 505;
  5. string grid[mxN];
  6. int hor[mxN][mxN], ver[mxN][mxN];
  7.  
  8. int main() {
  9. 	int n, m;
  10. 	cin >> n >> m;
  11. 	for(int i = 1; i <= n; ++i)
  12. 		cin >> grid[i], grid[i] = 'a' + grid[i];
  13. 	for(int i = 1; i <= n; ++i) {
  14. 		for(int j = 1; j <= m; ++j) {
  15. 			if(grid[i][j] == grid[i][j + 1] && grid[i][j] == '.')
  16. 				hor[i][j] = 1;
  17. 		}
  18. 	}
  19. 	grid[n + 1] = "";
  20. 	for(int i = 1; i <= m; ++i)
  21. 		grid[n + 1] += 'a';
  22. 	for(int i = 1; i <= n; ++i)
  23. 		for(int j = 1; j <= m; ++j)
  24. 			if(grid[i][j] == grid[i + 1][j] && grid[i][j] == '.')
  25. 				ver[i][j] = 1;
  26. 	for(int i = 1; i <= n; ++i) {
  27. 		for(int j = 1; j <= m; ++j) {
  28. 			ver[i][j] += ver[i - 1][j] + ver[i][j - 1] - ver[i - 1][j - 1];
  29. 			hor[i][j] += hor[i - 1][j] + hor[i][j - 1] - hor[i - 1][j - 1];
  30. 		}
  31. 	}
  32. 	int q;
  33. 	cin >> q;
  34. 	while(q--) {
  35. 		int r, c, r1, c1;
  36. 		scanf("%d%d%d%d", &r, &c, &r1, &c1);
  37. 		int answer = hor[r1][c1] - hor[r - 1][c1] - hor[r1][c - 1] + hor[r - 1][c - 1];
  38. 		answer += ver[r1][c1] - ver[r - 1][c1] - ver[r1][c - 1] + ver[r - 1][c - 1];
  39. 		printf("%d\n", answer);
  40. 	}
  41. }
  42.  
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
stdout
copy 
7
0
14
15
https://ideone.com/fEtTUp
language:
C++ (gcc 8.3)
created:
3 years 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!