fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. void answer(int count) {
  4. 	printf("%d\n", count);
  5. }
  6.  
  7. #define Y_SIZE (300)
  8. #define X_SIZE (300)
  9.  
  10. int H; // ホーム画面縦の区画数
  11. int W; // ホーム画面横の区画数
  12. int array[Y_SIZE][X_SIZE]; // ホーム画面の配置
  13. int vert_len[Y_SIZE][X_SIZE]; // 縦方向の区画の長さ
  14. int hori_len[Y_SIZE][X_SIZE]; // 横方向の区画の長さ
  15. int cache[Y_SIZE][X_SIZE]; // 答えのキャッシュ
  16.  
  17. int resolve_hori(S, T)
  18. 	int S; // ウィジェットの縦サイズ
  19. 	int T; // ウィジェットの横サイズ
  20. {
  21. 	int count, len;
  22. 	int x, y;
  23.  
  24. 	count = 0;
  25. 	for (y = 0; y <= H - S; y++) {
  26. 		for (x = 0; x < W;) {
  27. 			if (hori_len[y][x] >= T) {
  28. 				for (len = 0; vert_len[y][x + len] >= S && len < hori_len[y][x]; len++);
  29. 				if (len >= T) {
  30. 					count += len - T + 1;
  31. 				}
  32. 				x += len + 1;
  33. 			} else if (hori_len[y][x] >= 0) {
  34. 				x += hori_len[y][x] + 1;
  35. 			} else {
  36. 				x -= hori_len[y][x];
  37. 			}
  38. 		}
  39. 	}
  40. 	return count;
  41. }
  42.  
  43. int resolve_vert(S, T)
  44. 	int S; // ウィジェットの縦サイズ
  45. 	int T; // ウィジェットの横サイズ
  46. {
  47. 	int count, len;
  48. 	int x, y;
  49.  
  50. 	count = 0;
  51. 	for (x = 0; x <= W - T; x++) {
  52. 		for (y = 0; y < H;) {
  53. 			if (vert_len[y][x] >= S) {
  54. 				for (len = 0; hori_len[y + len][x] >= T && len < vert_len[y][x]; len++);
  55. 				if (len >= S) {
  56. 					count += len - S + 1;
  57. 				}
  58. 				y += len + 1;
  59. 			} else if (vert_len[y][x] >= 0) {
  60. 				y += vert_len[y][x] + 1;
  61. 			} else {
  62. 				y -= vert_len[y][x];
  63. 			}
  64. 		}
  65. 	}
  66. 	return count;
  67. }
  68.  
  69. void resolve(S, T)
  70. 	int S; // ウィジェットの縦サイズ
  71. 	int T; // ウィジェットの横サイズ
  72. {
  73. 	if (cache[S - 1][T - 1] < 0) {
  74. 		if (S < T) {
  75. 			cache[S - 1][T - 1] = resolve_hori(S, T);
  76. 		} else {
  77. 			cache[S - 1][T - 1] = resolve_vert(S, T);
  78. 		}
  79. 	}
  80. 	answer(cache[S - 1][T - 1]);
  81. }
  82.  
  83. int main(void) {
  84. 	char str[305];
  85. 	int N, s, t;
  86. 	int x, y, i;
  87. 	int len;
  88.  
  89. 	scanf("%d %d", &H, &W);
  90.  
  91. 	for (y = 0; y < H; y++) {
  92. 		scanf("%s", str);
  93. 		for (x = 0; x < W; x++) {
  94. 			array[y][x] = (int)(str[x] - '0');
  95. 		}
  96. 	}
  97.  
  98. 	for (x = 0; x < W; x++) {
  99. 		len = 0;
  100. 		for (y = H - 1; y >= 0; y--) {
  101. 			if (array[y][x]) {
  102. 				if (len > 0) {
  103. 					len = 0;
  104. 				}
  105. 				len--;
  106. 			} else {
  107. 				if (len < 0) {
  108. 					len = 0;
  109. 				}
  110. 				len++;
  111. 			}
  112. 			vert_len[y][x] = len;
  113. 		}
  114. 	}
  115.  
  116. 	for (y = 0; y < H; y++) {
  117. 		len = 0;
  118. 		for (x = W - 1; x >= 0; x--) {
  119. 			if (array[y][x]) {
  120. 				if (len > 0) {
  121. 					len = 0;
  122. 				}
  123. 				len--;
  124. 			} else {
  125. 				if (len < 0) {
  126. 					len = 0;
  127. 				}
  128. 				len++;
  129. 			}
  130. 			hori_len[y][x] = len;
  131. 		}
  132. 	}
  133.  
  134. 	for (y = 0; y < H; y++) {
  135. 		for (x = 0; x < W; x++) {
  136. 			cache[y][x] = -1;
  137. 		}
  138. 	}
  139.  
  140. 	scanf("%d", &N);
  141.  
  142. 	for (i = 0; i < N; i++) {
  143. 		scanf("%d %d", &s, &t);
  144.  
  145. 		resolve(s, t);
  146. 	}
  147.  
  148. 	return 0;
  149. }
  150.  
Success #stdin #stdout 0s 3700KB
comments (?)
stdin
copy 
7 4
1000
1101
1001
1111
1111
1111
1111
5
1 2
1 2
2 3
2 1
2 1
stdout
copy 
3
3
0
2
2
https://ideone.com/ZQHbO5
language:
C (gcc 8.3)
created:
10 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!