fork download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/bf7a5ec80e12edba64c30dabdd93a807
  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[][] space2left = new int[H][W];
  22. 		int[][] space2top = new int[H][W];
  23. 		int spacecount = 0;
  24.  
  25. 		Position[] startposition2left = new Position[H * W];
  26. 		Position[] startposition2top = new Position[H * W];
  27. 		int splCount = 0;
  28. 		int sptCount = 0;
  29.  
  30. 		for (int y = 0; y < H; y++)
  31. 		{
  32. 			String line = in.readLine();
  33. 			int space2leftSize = 0;
  34. 			for (int x = 0; x < W; x++)
  35. 			{
  36. 				char ch = line.charAt(x);
  37. 				if (ch == '1')
  38. 				{
  39. 					space2leftSize = 0;
  40. 					space2top[y][x] = 0;
  41. 					if (x > 0 && space2left[y][x - 1] > 0)
  42. 					{
  43. 						startposition2left[splCount++] = 
  44. 							Position.getPosition(y, x - 1);
  45. 					}
  46. 					if (y > 0 && space2top[y - 1][x] > 0)
  47. 					{
  48. 						startposition2top[sptCount++] = 
  49. 							Position.getPosition(y - 1, x);
  50. 					}
  51. 				}
  52. 				else // if (ch == '0')
  53. 				{
  54. 					spacecount++;
  55. 					space2leftSize++;
  56. 					if (y > 0)
  57. 					{
  58. 						space2top[y][x] = space2top[y - 1][x] + 1;
  59. 						if (y == H - 1)
  60. 						{
  61. 							startposition2top[sptCount++] = 
  62. 								Position.getPosition(y, x);
  63. 						}
  64. 					}
  65. 					else // if (y == 0)
  66. 					{
  67. 						space2top[y][x] = 1;
  68. 					}
  69. 					if (x == W - 1)
  70. 					{
  71. 						startposition2left[splCount++] =
  72. 							Position.getPosition(y, x);
  73. 					}
  74. 				}
  75. 				space2left[y][x] = space2leftSize;
  76. 			}
  77. 		}
  78. 		// print2dArray(space2left);
  79. 		// print2dArray(space2top);
  80. 		// System.out.println(startposition2left);
  81. 		// System.out.println(startposition2top);
  82.  
  83. 		final int N = Integer.valueOf(in.readLine()); // ウィジェット数
  84. 		HashSet<Position> placeablePosition = new HashSet<Position>(H * W);
  85. 		Map<Position, Integer> result = new HashMap<Position, Integer>(N);
  86.  
  87. 		for (int i = 0; i < N; i++)
  88. 		{
  89. 			String[] st = in.readLine().split(" ");
  90. 			int s = Integer.parseInt(st[0]); // ウィジェットの縦サイズ
  91. 			int t = Integer.parseInt(st[1]); // ウィジェットの横サイズ
  92. 			Position key = Position.getPosition(s, t);
  93. 			Integer value;
  94. 			if ((value = result.get(key)) != null)
  95. 			{
  96. 				System.out.println(value.intValue());
  97. 				continue;
  98. 			}
  99. 			int placeableCount = 0;
  100.  
  101. 			if (s == 1) // 横長のウィジェット
  102. 			{
  103. 				if (t == 1) // 1x1のウィジェット
  104. 				{
  105. 					placeableCount = spacecount;
  106. 				}
  107. 				else // if (t != 1) // 横長のウィジェット
  108. 				{
  109. 					for (int spl = 0; spl < splCount; ++spl)
  110. 					{
  111. 						Position position = startposition2left[spl];
  112. 						int spaceWSize = space2left[position.y][position.x];
  113. 						if (spaceWSize >= t)
  114. 						{
  115. 							placeableCount += spaceWSize - t + 1;
  116. 						}
  117. 					}
  118. 				}
  119. 			}
  120. 			else if (t == 1) // 縦長のウィジェット
  121. 			{
  122. 				for (int spt = 0; spt < sptCount; ++spt)
  123. 				{
  124. 					Position position = startposition2top[spt];
  125. 					int spaceHSize = space2top[position.y][position.x];
  126. 					if (spaceHSize >= s)
  127. 					{
  128. 						placeableCount += spaceHSize - s + 1;
  129. 					}
  130. 				}
  131. 			}
  132. 			else // if (s != 1 && t != 1)
  133. 			{
  134. 				placeablePosition.clear();
  135. 				// 横に走査していく
  136. 				for (int spl = 0; spl < splCount; ++spl)
  137. 				{
  138. 					Position position = startposition2left[spl];
  139. 					int spaceWSize = space2left[position.y][position.x];
  140. 					for (int dx = 0; dx < spaceWSize; ++dx)
  141. 					{
  142. 						int x = position.x - dx;
  143. 						int spaceHSize = space2top[position.y][x];
  144. 						if (spaceHSize < s)
  145. 						{
  146. 							continue; // 縦サイズが足りない
  147. 						}
  148. 						// 縦に走査して横サイズ以上の連続する空所を数える
  149. 						int count = 0;
  150. 						for (int dy = 0; dy < spaceHSize; ++dy)
  151. 						{
  152. 							int y = position.y - dy;
  153. 							if (space2left[y][x] >= t) 
  154. 							{
  155. 								count++;
  156. 								if (count >= s) // ウィジェットが確保できる
  157. 								{
  158. 									boolean placed = placeablePosition.add(
  159. 														Position.getPosition(y, x));
  160. 									if (placed == false)
  161. 									{
  162. 										break; // これ以上の縦の走査は走査済み
  163. 									}
  164. 								}
  165. 							}
  166. 							else
  167. 							{
  168. 								count = 0; // 連続の途切れ
  169. 							}
  170. 						}
  171. 					}
  172. 				}
  173. 				placeableCount = placeablePosition.size();
  174. 			}
  175. 			System.out.println(placeableCount);
  176. 			result.put(key, Integer.valueOf(placeableCount));
  177. 		}
  178.  
  179. 	} // end of main(String[])
  180.  
  181. 	static void print2dArray(int[][] array)
  182. 	{
  183. 		for (int i = 0; i < array.length; i++)
  184. 		{
  185. 			for (int j = 0; j < array[i].length; j++)
  186. 			{
  187. 				System.out.print(array[i][j] + " ");
  188. 			}
  189. 			System.out.println();
  190. 		}
  191. 		System.out.println();
  192. 	}
  193.  
  194. 	static class Position
  195. 	{
  196. 		static Position[] pool = new Position[90000];
  197. 		static Position getPosition(int y, int x)
  198. 		{
  199. 			int index = y * 300 + x;
  200. 			if (pool[index] == null)
  201. 			{
  202. 				pool[index] = new Position(y, x);
  203. 			}
  204. 			return pool[index];
  205. 		}		
  206.  
  207. 		final int y;
  208. 		final int x;
  209. 		private Position(int y, int x)
  210. 		{
  211. 			this.y = y;
  212. 			this.x = x;
  213. 		}
  214.  
  215. 		@Override public String toString()
  216. 		{
  217. 			return "(" + x + ", " + y + ")";
  218. 		}
  219.  
  220. 		@Override public int hashCode()
  221. 		{
  222. 			return y ^ x;
  223. 		}
  224.  
  225. 		@Override public boolean equals(Object obj)
  226. 		{
  227. 			Position pos = (Position)obj;
  228. 			return y == pos.y && x == pos.x;
  229. 		}
  230. 	} // end of class Position
  231. }
  232.  
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/H5WRDE
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!