fork download
copy 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/a29b5a39cf6ef5b2fbb4f8ae472ff275
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.util.*;
  7. import java.lang.*;
  8. import java.io.*;
  9.  
  10. class Main
  11. {
  12. 	public static void main (String[] args) throws java.lang.Exception
  13. 	{
  14. 		BufferedReader in = new BufferedReader(
  15. 			new InputStreamReader(System.in));
  16.  
  17. 		String[] hw = in.readLine().split(" ");
  18. 		final int H = Integer.parseInt(hw[0]); // ホーム画面縦の区画数
  19. 		final int W = Integer.parseInt(hw[1]); // ホーム画面横の区画数
  20.  
  21. 		int[][] home = new int[H][W];
  22. 		int[][] hoge = new int[H][W];
  23. 		int spacecount = 0;
  24.  
  25. 		for (int y = 0; y < H; y++)
  26. 		{
  27. 			String line = in.readLine();
  28. 			int count = 0;
  29. 			for (int x = 0; x < W; x++)
  30. 			{
  31. 				int tx = W - x - 1;
  32. 				char ch = line.charAt(tx);
  33. 				if (ch == '0')
  34. 				{
  35. 					spacecount++;
  36. 					count++;
  37. 					if (y > 0)
  38. 					{
  39. 						hoge[y][tx] = hoge[y - 1][tx] + 1;
  40. 					}
  41. 					else
  42. 					{
  43. 						hoge[y][tx] = hoge[y][tx] = 1;
  44. 					}
  45. 				}
  46. 				else
  47. 				{
  48. 					count = 0;
  49. 					hoge[y][tx] = 0;
  50. 				}
  51. 				home[y][tx] = count;
  52. 			}
  53. 		}
  54.  
  55. 		final int N = Integer.parseInt(in.readLine()); // ウィジェット数
  56.  
  57.  
  58. 		int[][] result = new int[300][300];
  59.  
  60. 		if (W > H)
  61. 		{		
  62. 			for (int i = 0; i < N; i++)
  63. 			{
  64. 				String[] st = in.readLine().split(" ");
  65. 				int s = Integer.parseInt(st[0]); // ウィジェットの縦サイズ
  66. 				int t = Integer.parseInt(st[1]); // ウィジェットの横サイズ
  67.  
  68. 				if (s > H || t > W)
  69. 				{
  70. 					System.out.println(0);
  71. 					continue;
  72. 				}
  73.  
  74. 				if (result[s][t] > 0)
  75. 				{
  76. 					System.out.println(result[s][t] - 1);
  77. 					continue;
  78. 				}
  79.  
  80. 				if (s == 1 && t == 1)
  81. 				{
  82. 					System.out.println(spacecount);
  83. 					continue;
  84. 				}
  85.  
  86. 				int count = 0;
  87.  
  88. 				for (int hy = H - 1; hy >= s - 1; hy--)
  89. 				{
  90. 					for (int hx = 0; hx < W - t + 1; hx++)
  91. 					{
  92. 						if (home[hy][hx] < t)
  93. 						{
  94. 							hx += home[hy][hx];
  95. 							continue;
  96. 						}
  97. 						if (hoge[hy][hx] < s)
  98. 						{
  99. 							continue;
  100. 						}
  101. 						int dy;
  102. 						for (dy = 1; dy < s; dy++)
  103. 						{
  104. 							int y = hy - dy;
  105. 							if (y >= H)
  106. 							{
  107. 								break;
  108. 							}
  109. 							if (home[y][hx] < t)
  110. 							{
  111. 								break;
  112. 							}
  113. 						}
  114. 						if (dy == s)
  115. 						{
  116. 							count++;
  117. 						}
  118. 					}
  119. 				}
  120. 				System.out.println(count);
  121. 				result[s][t] = count + 1;
  122. 			}
  123. 		}
  124. 		else
  125. 		{
  126. 			for (int i = 0; i < N; i++)
  127. 			{
  128. 				String[] st = in.readLine().split(" ");
  129. 				int s = Integer.parseInt(st[0]); // ウィジェットの縦サイズ
  130. 				int t = Integer.parseInt(st[1]); // ウィジェットの横サイズ
  131.  
  132. 				if (s > H || t > W)
  133. 				{
  134. 					System.out.println(0);
  135. 					continue;
  136. 				}
  137.  
  138. 				if (result[s][t] > 0)
  139. 				{
  140. 					System.out.println(result[s][t] - 1);
  141. 					continue;
  142. 				}
  143.  
  144. 				if (s == 1 && t == 1)
  145. 				{
  146. 					System.out.println(spacecount);
  147. 					continue;
  148. 				}
  149.  
  150. 				int count = 0;
  151.  
  152. 				for (int hx = 0; hx < W - t + 1; hx++)
  153. 				{
  154. 					for (int hy = H - 1; hy >= s - 1; hy--)
  155. 					{
  156. 						if (home[hy][hx] < t)
  157. 						{
  158. 							continue;
  159. 						}
  160. 						if (hoge[hy][hx] < s)
  161. 						{
  162. 							hy -= hoge[hy][hx];
  163. 							continue;
  164. 						}
  165. 						int dy;
  166. 						for (dy = 1; dy < s; dy++)
  167. 						{
  168. 							int y = hy - dy;
  169. 							if (y >= H)
  170. 							{
  171. 								break;
  172. 							}
  173. 							if (home[y][hx] < t)
  174. 							{
  175. 								break;
  176. 							}
  177. 						}
  178. 						if (dy == s)
  179. 						{
  180. 							count++;
  181. 						}
  182. 					}
  183. 				}
  184. 				System.out.println(count);
  185. 				result[s][t] = count + 1;
  186. 			}
  187. 		}
  188.  
  189. 	} // end of main(String[])
  190.  
  191. }
  192.  
Success #stdin #stdout 0.08s 380160KB
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/aJewvf
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

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!