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