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.  
  16. void resolve_hori(S, T)
  17. 	int S; // ウィジェットの縦サイズ
  18. 	int T; // ウィジェットの横サイズ
  19. {
  20. 	int count, len;
  21. 	int x, y, yy;
  22.  
  23. 	count = 0;
  24. 	yy = H - S;
  25. 	for (y = 0; y <= yy; y++) {
  26. 		len = 0;
  27. 		for (x = 0; x < W;) {
  28. 			if ((!len && hori_len[y][x] >= T) || (len && hori_len[y][x] > 0)) {
  29. 				if (vert_len[y][x] >= S) {
  30. 					if (++len >= T) {
  31. 						count++;
  32. 					}
  33. 				} else {
  34. 					len = 0;
  35. 				}
  36. 				x++;
  37. 			} else {
  38. 				len = 0;
  39. 				if (hori_len[y][x] > 0) {
  40. 					x += hori_len[y][x];
  41. 				} else {
  42. 					x -= hori_len[y][x];
  43. 				}
  44. 			}
  45. 		}
  46. 	}
  47. 	answer(count);
  48. }
  49.  
  50. void resolve_vert(S, T)
  51. 	int S; // ウィジェットの縦サイズ
  52. 	int T; // ウィジェットの横サイズ
  53. {
  54. 	int count, len;
  55. 	int x, y, xx;
  56.  
  57. 	count = 0;
  58. 	xx = W - T;
  59. 	for (x = 0; x <= xx; x++) {
  60. 		len = 0;
  61. 		for (y = 0; y < H;) {
  62. 			if ((!len && vert_len[y][x] >= S) || (len && vert_len[y][x] > 0)) {
  63. 				if (hori_len[y][x] >= T) {
  64. 					if (++len >= S) {
  65. 						count++;
  66. 					}
  67. 				} else {
  68. 					len = 0;
  69. 				}
  70. 				y++;
  71. 			} else {
  72. 				len = 0;
  73. 				if (vert_len[y][x] > 0) {
  74. 					y += vert_len[y][x];
  75. 				} else {
  76. 					y -= vert_len[y][x];
  77. 				}
  78. 			}
  79. 		}
  80. 	}
  81. 	answer(count);
  82. }
  83.  
  84. void resolve(S, T)
  85. 	int S; // ウィジェットの縦サイズ
  86. 	int T; // ウィジェットの横サイズ
  87. {
  88. 	if (S < T) {
  89. 		resolve_hori(S, T);
  90. 	} else {
  91. 		resolve_vert(S, T);
  92. 	}
  93. }
  94.  
  95. int main(void) {
  96. 	char str[305];
  97. 	int N, s, t;
  98. 	int x, y, i;
  99. 	int len;
  100.  
  101. 	scanf("%d %d", &H, &W);
  102.  
  103. 	for (y = 0; y < H; y++) {
  104. 		scanf("%s", str);
  105. 		for (x = 0; x < W; x++) {
  106. 			array[y][x] = (int)(str[x] - '0');
  107. 		}
  108. 	}
  109.  
  110. 	for (x = 0; x < W; x++) {
  111. 		len = 0;
  112. 		for (y = H - 1; y >= 0; y--) {
  113. 			if (array[y][x]) {
  114. 				if (len > 0) {
  115. 					len = 0;
  116. 				}
  117. 				len--;
  118. 			} else {
  119. 				if (len < 0) {
  120. 					len = 0;
  121. 				}
  122. 				len++;
  123. 			}
  124. 			vert_len[y][x] = len;
  125. 		}
  126. 	}
  127.  
  128. 	for (y = 0; y < H; y++) {
  129. 		len = 0;
  130. 		for (x = W - 1; x >= 0; x--) {
  131. 			if (array[y][x]) {
  132. 				if (len > 0) {
  133. 					len = 0;
  134. 				}
  135. 				len--;
  136. 			} else {
  137. 				if (len < 0) {
  138. 					len = 0;
  139. 				}
  140. 				len++;
  141. 			}
  142. 			hori_len[y][x] = len;
  143. 		}
  144. 	}
  145.  
  146. 	scanf("%d", &N);
  147.  
  148. 	for (i = 0; i < N; i++) {
  149. 		scanf("%d %d", &s, &t);
  150.  
  151. 		resolve(s, t);
  152. 	}
  153.  
  154. 	return 0;
  155. }
  156.  
Success #stdin #stdout 0s 3304KB
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/BKKTN0
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!