fork(1) download
copy 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/714a2ecac3cdedf713638e16df467dbb
  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(new InputStreamReader(System.in));
  15.  
  16. 		String[] hw = in.readLine().split(" ");
  17. 		final int H = Integer.parseInt(hw[0]);
  18. 		final int W = Integer.parseInt(hw[1]);
  19.  
  20. 		int[][] space2left = new int[H][W];
  21. 		int[][] space2top = new int[H][W];
  22. 		int allSpaceCount = 0;
  23.  
  24. 		int[] startPointX = new int[H * (1 + W / 3)];
  25. 		int[] startPointY = new int[H * (1 + W / 3)];
  26. 		int startPointCount = 0;
  27.  
  28. 		int[] space2leftCount = new int[W + 1];
  29. 		int[] space2topCount = new int[H + 1];
  30.  
  31. 		for (int y = 0; y < H; y++)
  32. 		{
  33. 			String line = in.readLine();
  34. 			int spaceCount = 0;
  35. 			for (int x = 0; x < W; x++)
  36. 			{
  37. 				char ch = line.charAt(x);
  38. 				if (ch == '0') // 空
  39. 				{
  40. 					spaceCount++;
  41. 					allSpaceCount++;
  42. 					if (y > 0)
  43. 					{
  44. 						space2top[y][x] = space2top[y - 1][x] + 1;
  45. 						if (y == H - 1 && space2top[y][x] > 1)
  46. 						{
  47. 							space2topCount[space2top[y][x]]++;
  48. 						}
  49. 					}
  50. 					else // if (y == 0) 
  51. 					{
  52. 						space2top[y][x] = 1;
  53. 					}
  54. 				}
  55. 				else // if (ch == '1') // 埋
  56. 				{
  57. 					if (spaceCount > 1)
  58. 					{
  59. 						startPointX[startPointCount] = x - 1;
  60. 						startPointY[startPointCount] = y;
  61. 						startPointCount++;
  62. 						space2leftCount[spaceCount]++;
  63. 					}
  64. 					spaceCount = 0;
  65. 					space2top[y][x] = 0;
  66. 					if (y > 0 && space2top[y - 1][x] > 1)
  67. 					{
  68. 						space2topCount[space2top[y - 1][x]]++;
  69. 					}
  70. 				}
  71. 				space2left[y][x] = spaceCount;
  72. 			} // for(x)
  73. 			if (spaceCount > 1)
  74. 			{
  75. 				startPointX[startPointCount] = W - 1;
  76. 				startPointY[startPointCount] = y;
  77. 				startPointCount++;
  78. 				space2leftCount[spaceCount]++;
  79. 			}
  80. 		} // for(y)
  81.  
  82. 		final int N = Integer.parseInt(in.readLine());
  83. 		int[][] result = new int[H + 1][W + 1];
  84.  
  85. 		for (int i = 0; i < N; i++)
  86. 		{
  87. 			String[] st = in.readLine().split(" ");
  88. 			int s = Integer.parseInt(st[0]);
  89. 			int t = Integer.parseInt(st[1]);
  90.  
  91. 			if (s > H || t > W)
  92. 			{
  93. 				System.out.println("0");
  94. 				continue;
  95. 			}
  96.  
  97. 			if (result[s][t] > 0)
  98. 			{
  99. 				System.out.println(result[s][t] - 1);
  100. 				continue;
  101. 			}
  102.  
  103. 			int count = 0;
  104.  
  105. 			if (s != 1 && t != 1)
  106. 			{
  107. 				for (int j = 0; j < startPointCount; j++)
  108. 				{
  109. 					int x = startPointX[j];
  110. 					int y = startPointY[j];
  111. 					int seekLength = space2left[y][x] - t + 1;
  112.  
  113. 					for (int dx = 0; dx < seekLength; dx++)
  114. 					{
  115. 						int tx = x - dx;
  116. 						if (tx < 0)
  117. 						{
  118. 							break;
  119. 						}
  120. 						if (space2top[y][tx] < s)
  121. 						{
  122. 							continue;
  123. 						}
  124. 						int dy;
  125. 						for (dy = 0; dy < s; dy++)
  126. 						{
  127. 							int ty = y - dy;
  128. 							if (ty < 0)
  129. 							{
  130. 								break;
  131. 							}
  132. 							if (space2left[ty][tx] < t)
  133. 							{
  134. 								break;
  135. 							}
  136. 						} // for(dy)
  137. 						if (dy == s)
  138. 						{
  139. 							count++;
  140. 						}
  141. 					} // for(dx)
  142. 				} // for(j)
  143. 			}
  144. 			else if (s != 1)
  145. 			{
  146. 				for (int j = s; j <= H; j++)
  147. 				{
  148. 					count += space2topCount[j] * (j - s + 1);
  149. 				}
  150. 			}
  151. 			else if (t != 1)
  152. 			{
  153. 				for (int j = t; j <= W; j++)
  154. 				{
  155. 					count += space2leftCount[j] * (j - t + 1);
  156. 				}
  157. 			}
  158. 			else // if (s == 1 && t == 1)
  159. 			{
  160. 				count = allSpaceCount;
  161. 			}
  162. 			System.out.println(count);
  163. 			result[s][t] = count + 1;
  164. 		} // for(i)
  165.  
  166. 	} // void main([String)
  167.  
  168. } // class Main
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
5 5
00000
00100
00010
10001
10000
7
2 2
1 1
3 2
3 2
2 3
3 1
1 3
stdout
copy 
6
20
2
2
1
6
7
https://ideone.com/qMS9pQ
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!