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 hori_emp_seg_len[Y_SIZE + 1][X_SIZE]; // 水平空き線分の長さ
  14. int hori_emp_seg_crs_len_min[Y_SIZE][X_SIZE]; // 水平空き線分と直交する垂直空き線分の長さの最小値
  15. int hori_emp_seg_crs_len_max[Y_SIZE][X_SIZE]; // 水平空き線分と直交する垂直空き線分の長さの最大値
  16. int hori_emp_seg_len_row_max[Y_SIZE]; // 水平空き線分の長さの行ごとの最大値
  17. int hori_fil_seg_len[Y_SIZE][X_SIZE]; // 水平埋め線分の長さ
  18. int vert_emp_seg_len[Y_SIZE][X_SIZE + 1]; // 垂直空き線分の長さ
  19. int vert_emp_seg_crs_len_min[Y_SIZE][X_SIZE]; // 垂直空き線分と直交する水平空き線分の長さの最小値
  20. int vert_emp_seg_crs_len_max[Y_SIZE][X_SIZE]; // 垂直空き線分と直交する水平空き線分の長さの最大値
  21. int vert_emp_seg_len_col_max[X_SIZE]; // 垂直空き線分の長さの列ごとの最大値
  22. int vert_fil_seg_len[Y_SIZE][X_SIZE]; // 垂直埋め線分の長さ
  23. int cache[Y_SIZE + 1][X_SIZE + 1]; // 配置可能座標の数のキャッシュ
  24.  
  25. int // 配置可能座標の数
  26. resolve_hori(S, T)
  27. 	int S; // ウィジェットの縦サイズ
  28. 	int T; // ウィジェットの横サイズ
  29. {
  30. 	int count, len;
  31. 	int x, y;
  32.  
  33. 	count = 0;
  34. 	for (y = 0; y <= H - S; y++) {
  35. 		if (hori_emp_seg_len_row_max[y] >= T) {
  36. 			for (x = 0; x < W;) {
  37. 				if (array[y][x]) {
  38. 					x += hori_fil_seg_len[y][x];
  39. 				} else if (hori_emp_seg_len[y][x] >= T) {
  40. 					if (hori_emp_seg_crs_len_min[y][x] >= S) {
  41. 						count += hori_emp_seg_len[y][x] - T + 1;
  42. 						x += hori_emp_seg_len[y][x] + 1;
  43. 					} else if (hori_emp_seg_crs_len_max[y][x] < S) {
  44. 						x += hori_emp_seg_len[y][x] + 1;
  45. 					} else {
  46. 						for (len = 0; vert_emp_seg_len[y][x + len] >= S; len++);
  47. 						if (len >= T) {
  48. 							count += len - T + 1;
  49. 						}
  50. 						x += len + 1;
  51. 					}
  52. 				} else {
  53. 					x += hori_emp_seg_len[y][x] + 1;
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. 	return count;
  59. }
  60.  
  61. int // 配置可能座標の数
  62. resolve_vert(S, T)
  63. 	int S; // ウィジェットの縦サイズ
  64. 	int T; // ウィジェットの横サイズ
  65. {
  66. 	int count, len;
  67. 	int x, y;
  68.  
  69. 	count = 0;
  70. 	for (x = 0; x <= W - T; x++) {
  71. 		if (vert_emp_seg_len_col_max[x] >= S) {
  72. 			for (y = 0; y < H;) {
  73. 				if (array[y][x]) {
  74. 					y += vert_fil_seg_len[y][x];
  75. 				} else if (vert_emp_seg_len[y][x] >= S) {
  76. 					if (vert_emp_seg_crs_len_min[y][x] >= T) {
  77. 						count += vert_emp_seg_len[y][x] - S + 1;
  78. 						y += vert_emp_seg_len[y][x] + 1;
  79. 					} else if (vert_emp_seg_crs_len_max[y][x] < T) {
  80. 						y += vert_emp_seg_len[y][x] + 1;
  81. 					} else {
  82. 						for (len = 0; hori_emp_seg_len[y + len][x] >= T; len++);
  83. 						if (len >= S) {
  84. 							count += len - S + 1;
  85. 						}
  86. 						y += len + 1;
  87. 					}
  88. 				} else {
  89. 					y += vert_emp_seg_len[y][x] + 1;
  90. 				}
  91. 			}
  92. 		}
  93. 	}
  94. 	return count;
  95. }
  96.  
  97. void resolve(S, T)
  98. 	int S; // ウィジェットの縦サイズ
  99. 	int T; // ウィジェットの横サイズ
  100. {
  101. 	if (cache[S][T] < 0) {
  102. 		if (S < T) {
  103. 			cache[S][T] = resolve_hori(S, T);
  104. 		} else {
  105. 			cache[S][T] = resolve_vert(S, T);
  106. 		}
  107. 	}
  108. 	answer(cache[S][T]);
  109. }
  110.  
  111. int main(void) {
  112. 	char str[305];
  113. 	int N, s, t;
  114. 	int x, y, i;
  115. 	int fil, len, len_min, len_max;
  116.  
  117. 	scanf("%d %d", &H, &W);
  118.  
  119. 	for (y = 0; y < H; y++) {
  120. 		scanf("%s", str);
  121. 		for (x = 0; x < W; x++) {
  122. 			array[y][x] = (int)(str[x] - '0');
  123. 		}
  124. 	}
  125.  
  126. 	for (y = 0; y < H; y++) {
  127. 		hori_emp_seg_len_row_max[y] = 0;
  128. 		fil = 0;
  129. 		len = 0;
  130. 		for (x = W - 1; x >= 0; x--) {
  131. 			if (array[y][x] == fil) {
  132. 				len++;
  133. 			} else {
  134. 				fil = array[y][x];
  135. 				len = 1;
  136. 			}
  137. 			if (fil) {
  138. 				hori_emp_seg_len[y][x] = 0;
  139. 				hori_fil_seg_len[y][x] = len;
  140. 			} else {
  141. 				hori_emp_seg_len[y][x] = len;
  142. 				hori_fil_seg_len[y][x] = 0;
  143. 				if (len > hori_emp_seg_len_row_max[y]) {
  144. 					hori_emp_seg_len_row_max[y] = len;
  145. 				}
  146. 			}
  147. 		}
  148. 	}
  149. 	for (x = 0; x < W; x++) {
  150. 		hori_emp_seg_len[H][x] = 0;
  151. 	}
  152.  
  153. 	for (x = 0; x < W; x++) {
  154. 		vert_emp_seg_len_col_max[x] = 0;
  155. 		fil = 0;
  156. 		len = 0;
  157. 		for (y = H - 1; y >= 0; y--) {
  158. 			if (array[y][x] == fil) {
  159. 				len++;
  160. 			} else {
  161. 				fil = array[y][x];
  162. 				len = 1;
  163. 			}
  164. 			if (fil) {
  165. 				vert_emp_seg_len[y][x] = 0;
  166. 				vert_fil_seg_len[y][x] = len;
  167. 			} else {
  168. 				vert_emp_seg_len[y][x] = len;
  169. 				vert_fil_seg_len[y][x] = 0;
  170. 				if (len > vert_emp_seg_len_col_max[x]) {
  171. 					vert_emp_seg_len_col_max[x] = len;
  172. 				}
  173. 			}
  174. 		}
  175. 	}
  176. 	for (y = 0; y < H; y++) {
  177. 		vert_emp_seg_len[y][W] = 0;
  178. 	}
  179.  
  180. 	for (y = 0; y < H; y++) {
  181. 		len_min = H;
  182. 		len_max = 0;
  183. 		for (x = W - 1; x >= 0; x--) {
  184. 			if (array[y][x]) {
  185. 				len_min = H;
  186. 				len_max = 0;
  187. 			} else {
  188. 				if (vert_emp_seg_len[y][x] < len_min) {
  189. 					len_min = vert_emp_seg_len[y][x];
  190. 				}
  191. 				if (vert_emp_seg_len[y][x] > len_max) {
  192. 					len_max = vert_emp_seg_len[y][x];
  193. 				}
  194. 				hori_emp_seg_crs_len_min[y][x] = len_min;
  195. 				hori_emp_seg_crs_len_max[y][x] = len_max;
  196. 			}
  197. 		}
  198. 	}
  199.  
  200. 	for (x = 0; x < W; x++) {
  201. 		len_min = W;
  202. 		len_max = 0;
  203. 		for (y = H - 1; y >= 0; y--) {
  204. 			if (array[y][x]) {
  205. 				len_min = W;
  206. 				len_max = 0;
  207. 			} else {
  208. 				if (hori_emp_seg_len[y][x] < len_min) {
  209. 					len_min = hori_emp_seg_len[y][x];
  210. 				}
  211. 				if (hori_emp_seg_len[y][x] > len_max) {
  212. 					len_max = hori_emp_seg_len[y][x];
  213. 				}
  214. 				vert_emp_seg_crs_len_min[y][x] = len_min;
  215. 				vert_emp_seg_crs_len_max[y][x] = len_max;
  216. 			}
  217. 		}
  218. 	}
  219.  
  220. 	for (y = 1; y <= H; y++) {
  221. 		for (x = 1; x <= W; x++) {
  222. 			cache[y][x] = -1;
  223. 		}
  224. 	}
  225.  
  226. 	scanf("%d", &N);
  227.  
  228. 	for (i = 0; i < N; i++) {
  229. 		scanf("%d %d", &s, &t);
  230.  
  231. 		resolve(s, t);
  232. 	}
  233.  
  234. 	return 0;
  235. }
  236.  
Success #stdin #stdout 0s 5816KB
comments (?)
stdin
copy 
7 4
1000
1101
1001
1111
1111
1111
1111
3
1 2
2 3
2 1
stdout
copy 
3
0
2
https://ideone.com/wJM5sv
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!