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. // 線分; あるセルから正方向に空き状態、または埋め状態が連続する領域
  11. typedef struct {
  12. 	int len; // 長さ
  13. 	int crs_emp_seg_len_min; // 直交する空き線分の長さの最小値
  14. 	int crs_emp_seg_len_max; // 直交する空き線分の長さの最大値
  15. } SEGMENT;
  16.  
  17. int H; // ホーム画面縦の区画数
  18. int W; // ホーム画面横の区画数
  19. int array[Y_SIZE][X_SIZE]; // ホーム画面の配置
  20. SEGMENT hori_segs[Y_SIZE][X_SIZE]; // 水平方向の線分
  21. SEGMENT vert_segs[Y_SIZE][X_SIZE]; // 垂直方向の線分
  22. int cache[Y_SIZE][X_SIZE]; // 答えのキャッシュ
  23.  
  24. int // 答え
  25. resolve_hori(S, T)
  26. 	int S; // ウィジェットの縦サイズ
  27. 	int T; // ウィジェットの横サイズ
  28. {
  29. 	int count, len;
  30. 	int x, y;
  31.  
  32. 	count = 0;
  33. 	for (y = 0; y <= H - S; y++) {
  34. 		for (x = 0; x < W;) {
  35. 			if (array[y][x]) {
  36. 				x += hori_segs[y][x].len;
  37. 			} else if (hori_segs[y][x].len >= T) {
  38. 				if (hori_segs[y][x].crs_emp_seg_len_min >= S) {
  39. 					count += hori_segs[y][x].len - T + 1;
  40. 					x += hori_segs[y][x].len + 1;
  41. 				} else if (hori_segs[y][x].crs_emp_seg_len_max < S) {
  42. 					x += hori_segs[y][x].len + 1;
  43. 				} else {
  44. 					for (len = 0; len < hori_segs[y][x].len && vert_segs[y][x + len].len >= S; len++);
  45. 					if (len >= T) {
  46. 						count += len - T + 1;
  47. 					}
  48. 					x += len + 1;
  49. 				}
  50. 			} else {
  51. 				x += hori_segs[y][x].len + 1;
  52. 			}
  53. 		}
  54. 	}
  55. 	return count;
  56. }
  57.  
  58. int // 答え
  59. resolve_vert(S, T)
  60. 	int S; // ウィジェットの縦サイズ
  61. 	int T; // ウィジェットの横サイズ
  62. {
  63. 	int count, len;
  64. 	int x, y;
  65.  
  66. 	count = 0;
  67. 	for (x = 0; x <= W - T; x++) {
  68. 		for (y = 0; y < H;) {
  69. 			if (array[y][x]) {
  70. 				y += vert_segs[y][x].len;
  71. 			} else if (vert_segs[y][x].len >= S) {
  72. 				if (vert_segs[y][x].crs_emp_seg_len_min >= T) {
  73. 					count += vert_segs[y][x].len - S + 1;
  74. 					y += vert_segs[y][x].len + 1;
  75. 				} else if (vert_segs[y][x].crs_emp_seg_len_max < T) {
  76. 					y += vert_segs[y][x].len + 1;
  77. 				} else {
  78. 					for (len = 0; len < vert_segs[y][x].len && hori_segs[y + len][x].len >= T; len++);
  79. 					if (len >= S) {
  80. 						count += len - S + 1;
  81. 					}
  82. 					y += len + 1;
  83. 				}
  84. 			} else {
  85. 				y += vert_segs[y][x].len + 1;
  86. 			}
  87. 		}
  88. 	}
  89. 	return count;
  90. }
  91.  
  92. void resolve(S, T)
  93. 	int S; // ウィジェットの縦サイズ
  94. 	int T; // ウィジェットの横サイズ
  95. {
  96. 	if (cache[S - 1][T - 1] < 0) {
  97. 		if (S < T) {
  98. 			cache[S - 1][T - 1] = resolve_hori(S, T);
  99. 		} else {
  100. 			cache[S - 1][T - 1] = resolve_vert(S, T);
  101. 		}
  102. 	}
  103. 	answer(cache[S - 1][T - 1]);
  104. }
  105.  
  106. int main(void) {
  107. 	char str[305];
  108. 	int N, s, t;
  109. 	int x, y, i;
  110. 	int fill, len, len_min, len_max;
  111.  
  112. 	scanf("%d %d", &H, &W);
  113.  
  114. 	for (y = 0; y < H; y++) {
  115. 		scanf("%s", str);
  116. 		for (x = 0; x < W; x++) {
  117. 			array[y][x] = (int)(str[x] - '0');
  118. 		}
  119. 	}
  120.  
  121. 	for (y = 0; y < H; y++) {
  122. 		fill = 0;
  123. 		len = 0;
  124. 		for (x = W - 1; x >= 0; x--) {
  125. 			if (array[y][x] == fill) {
  126. 				len++;
  127. 			} else {
  128. 				fill = array[y][x];
  129. 				len = 1;
  130. 			}
  131. 			hori_segs[y][x].len = len;
  132. 		}
  133. 	}
  134.  
  135. 	for (x = 0; x < W; x++) {
  136. 		fill = 0;
  137. 		len = 0;
  138. 		for (y = H - 1; y >= 0; y--) {
  139. 			if (array[y][x] == fill) {
  140. 				len++;
  141. 			} else {
  142. 				fill = array[y][x];
  143. 				len = 1;
  144. 			}
  145. 			vert_segs[y][x].len = len;
  146. 		}
  147. 	}
  148.  
  149. 	for (y = 0; y < H; y++) {
  150. 		len_min = Y_SIZE;
  151. 		len_max = 0;
  152. 		for (x = W - 1; x >= 0; x--) {
  153. 			if (array[y][x]) {
  154. 				len_min = Y_SIZE;
  155. 				len_max = 0;
  156. 			} else {
  157. 				if (vert_segs[y][x].len < len_min) {
  158. 					len_min = vert_segs[y][x].len;
  159. 				}
  160. 				if (vert_segs[y][x].len > len_max) {
  161. 					len_max = vert_segs[y][x].len;
  162. 				}
  163. 				hori_segs[y][x].crs_emp_seg_len_min = len_min;
  164. 				hori_segs[y][x].crs_emp_seg_len_max = len_max;
  165. 			}
  166. 		}
  167. 	}
  168.  
  169. 	for (x = 0; x < W; x++) {
  170. 		len_min = X_SIZE;
  171. 		len_max = 0;
  172. 		for (y = H - 1; y >= 0; y--) {
  173. 			if (array[y][x]) {
  174. 				len_min = X_SIZE;
  175. 				len_max = 0;
  176. 			} else {
  177. 				if (hori_segs[y][x].len < len_min) {
  178. 					len_min = hori_segs[y][x].len;
  179. 				}
  180. 				if (hori_segs[y][x].len > len_max) {
  181. 					len_max = hori_segs[y][x].len;
  182. 				}
  183. 				vert_segs[y][x].crs_emp_seg_len_min = len_min;
  184. 				vert_segs[y][x].crs_emp_seg_len_max = len_max;
  185. 			}
  186. 		}
  187. 	}
  188.  
  189. 	for (y = 0; y < H; y++) {
  190. 		for (x = 0; x < W; x++) {
  191. 			cache[y][x] = -1;
  192. 		}
  193. 	}
  194.  
  195. 	scanf("%d", &N);
  196.  
  197. 	for (i = 0; i < N; i++) {
  198. 		scanf("%d %d", &s, &t);
  199.  
  200. 		resolve(s, t);
  201. 	}
  202.  
  203. 	return 0;
  204. }
  205.  
Success #stdin #stdout 0s 5108KB
comments (?)
stdin
copy 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout
copy 
6
20
2
https://ideone.com/Qq90e7
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!