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