fork download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/f04b30e0fb57780d36311c5cf5f99d27
  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. 		int maxhome = 0;
  25. 		int maxhoge = 0;
  26.  
  27. 		for (int y = 0; y < H; y++)
  28. 		{
  29. 			String line = in.readLine();
  30. 			int count = 0;
  31. 			for (int x = 0; x < W; x++)
  32. 			{
  33. 				int tx = W - x - 1;
  34. 				char ch = line.charAt(tx);
  35. 				if (ch == '0')
  36. 				{
  37. 					spacecount++;
  38. 					count++;
  39. 					if (y > 0)
  40. 					{
  41. 						hoge[y][tx] = hoge[y - 1][tx] + 1;
  42. 						if (hoge[y][tx] > maxhoge)
  43. 						{
  44. 							maxhoge = hoge[y][tx];
  45. 						}
  46. 					}
  47. 					else
  48. 					{
  49. 						hoge[y][tx] = hoge[y][tx] = 1;
  50. 					}
  51. 					if (count > maxhome)
  52. 					{
  53. 						maxhome = count;
  54. 					}
  55. 				}
  56. 				else
  57. 				{
  58. 					count = 0;
  59. 					hoge[y][tx] = 0;
  60. 				}
  61. 				home[y][tx] = count;
  62. 			}
  63. 		}
  64.  
  65. 		final int N = Integer.parseInt(in.readLine()); // ウィジェット数
  66.  
  67. 		int[][] result = new int[300][300];
  68.  
  69. 		for (int i = 0; i < N; i++)
  70. 		{
  71. 			String[] st = in.readLine().split(" ");
  72. 			int s = Integer.parseInt(st[0]); // ウィジェットの縦サイズ
  73. 			int t = Integer.parseInt(st[1]); // ウィジェットの横サイズ
  74.  
  75. 			if (s > maxhoge || t > maxhome)
  76. 			{
  77. 				System.out.println(0);
  78. 				continue;
  79. 			}
  80.  
  81. 			if (result[s][t] > 0)
  82. 			{
  83. 				System.out.println(result[s][t] - 1);
  84. 				continue;
  85. 			}
  86.  
  87. 			if (s == 1 && t == 1)
  88. 			{
  89. 				System.out.println(spacecount);
  90. 				continue;
  91. 			}
  92.  
  93. 			int count = 0;
  94. 			if (W > H)
  95. 			{
  96. 				for (int hy = H - 1; hy >= s - 1; hy--)
  97. 				{
  98. 					for (int hx = 0; hx < W - t + 1; hx++)
  99. 					{
  100. 						if (home[hy][hx] < t)
  101. 						{
  102. 							hx += home[hy][hx];
  103. 							continue;
  104. 						}
  105. 						if (hoge[hy][hx] < s)
  106. 						{
  107. 							continue;
  108. 						}
  109. 						int dy;
  110. 						for (dy = 1; dy < s; dy++)
  111. 						{
  112. 							int y = hy - dy;
  113. 							if (y >= H)
  114. 							{
  115. 								break;
  116. 							}
  117. 							if (home[y][hx] < t)
  118. 							{
  119. 								break;
  120. 							}
  121. 						}
  122. 						if (dy == s)
  123. 						{
  124. 							count++;
  125. 						}
  126. 					}
  127. 				}
  128. 			}
  129. 			else
  130. 			{
  131. 				for (int hx = 0; hx < W - t + 1; hx++)
  132. 				{
  133. 					for (int hy = H - 1; hy >= s - 1; hy--)
  134. 					{
  135. 						if (home[hy][hx] < t)
  136. 						{
  137. 							continue;
  138. 						}
  139. 						if (hoge[hy][hx] < s)
  140. 						{
  141. 							hy -= hoge[hy][hx];
  142. 							continue;
  143. 						}
  144. 						int dy;
  145. 						for (dy = 1; dy < s; dy++)
  146. 						{
  147. 							int y = hy - dy;
  148. 							if (y >= H)
  149. 							{
  150. 								break;
  151. 							}
  152. 							if (home[y][hx] < t)
  153. 							{
  154. 								break;
  155. 							}
  156. 						}
  157. 						if (dy == s)
  158. 						{
  159. 							count++;
  160. 						}
  161. 					}
  162. 				}
  163. 			}
  164. 			System.out.println(count);
  165. 			result[s][t] = count + 1;
  166. 		}
  167.  
  168. 	} // end of main(String[])
  169.  
  170. }
  171.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/V37Bc2
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!