fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.ListIterator;
  6. import java.util.TreeSet;
  7.  
  8. class Main {
  9. 	static class Size implements Comparable {
  10. 		int width, height;
  11.  
  12. 		Size(int width, int height) {
  13. 			this.width = width;
  14. 			this.height = height;
  15. 		}
  16.  
  17. 		int getArea() {
  18. 			return width * height;
  19. 		}
  20.  
  21. 		Size intersect(Size size) {
  22. 			return new Size(Math.min(width, size.width), Math.min(height, size.height));
  23. 		}
  24.  
  25. 		boolean contain(Size size) {
  26. 			return size.width <= width && size.height <= height;
  27. 		}
  28.  
  29. 		@Override
  30. 		public int compareTo(Object object) {
  31. 			Size size = (Size)object;
  32. 			int area = getArea();
  33. 			int anotherArea = size.getArea();
  34. 			if (area == anotherArea) {
  35. 				if (width == size.width) {
  36. 					return height - size.height;
  37. 				} else {
  38. 					return width - size.width;
  39. 				}
  40. 			} else {
  41. 				return area - anotherArea;
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	static class Matrix implements Cloneable {
  47. 		boolean[][] components;
  48.  
  49. 		Matrix(boolean[][] components) {
  50. 			this.components = components;
  51. 		}
  52.  
  53. 		void convolve(int columns, int rows) {
  54. 			if (columns > 0) {
  55. 				for (int y = 0; y < components.length; y++) {
  56. 					int length = columns;
  57. 					for (int x = components[0].length - 1; x >= 0; x--) {
  58. 						if (components[y][x]) {
  59. 							length = columns;
  60. 						} else if (length > 0) {
  61. 							components[y][x] = true;
  62. 							length--;
  63. 						}
  64. 					}
  65. 				}
  66. 			}
  67. 			if (rows > 0) {
  68. 				for (int x = 0; x < components[0].length; x++) {
  69. 					int length = rows;
  70. 					for (int y = components.length - 1; y >= 0; y--) {
  71. 						if (components[y][x]) {
  72. 							length = rows;
  73. 						} else if (length > 0) {
  74. 							components[y][x] = true;
  75. 							length--;
  76. 						}
  77. 					}
  78. 				}
  79. 			}
  80. 		}
  81.  
  82. 		int countup() {
  83. 			int count = 0;
  84. 			for (int y = 0; y < components.length; y++) {
  85. 				for (int x = 0; x < components[0].length; x++) {
  86. 					if (!components[y][x]) {
  87. 						count++;
  88. 					}
  89. 				}
  90. 			}
  91. 			return count;
  92. 		}
  93.  
  94. 		@Override
  95. 		public Matrix clone() {
  96. 			Matrix matrix = null;
  97. 			try {
  98. 				matrix = (Matrix)super.clone();
  99. 				matrix.components = new boolean[components.length][components[0].length];
  100. 				for (int y = 0; y < components.length; y++) {
  101. 					for (int x = 0; x < components[0].length; x++) {
  102. 						matrix.components[y][x] = components[y][x];
  103. 					}
  104. 				}
  105. 			} catch (CloneNotSupportedException cnse) {}
  106. 			return matrix;
  107. 		}
  108. 	}
  109.  
  110. 	static class Node implements Comparable {
  111. 		boolean widget;
  112. 		Size size;
  113. 		List<Node> children;
  114.  
  115. 		Node(boolean widget, Size size) {
  116. 			this.widget = widget;
  117. 			this.size = size;
  118. 			children = new ArrayList<Node>();
  119. 		}
  120.  
  121. 		void visit(Matrix parentMatrix, Size parentSize) {
  122. 			Matrix matrix = parentMatrix.clone();
  123. 			matrix.convolve(size.width - parentSize.width, size.height - parentSize.height);
  124. 			if (widget) {
  125. 				counts[size.height][size.width] = new Integer(matrix.countup());
  126. 			}
  127. 			ListIterator<Node> iter = children.listIterator();
  128. 			while (iter.hasNext()) {
  129. 				iter.next().visit(matrix, size);
  130. 			}
  131. 		}
  132.  
  133. 		@Override
  134. 		public int compareTo(Object object) {
  135. 			return size.compareTo(((Node)object).size);
  136. 		}
  137. 	}
  138.  
  139. 	public static void main(String[] args) throws Exception {
  140. 		new Main().run();
  141. 	}
  142.  
  143. 	final static int MAX_WIDTH = 300;
  144. 	final static int MAX_HEIGHT = 300;
  145. 	final static Integer[][] counts = new Integer[MAX_HEIGHT + 1][MAX_WIDTH + 1];
  146.  
  147. 	void run() throws Exception {
  148. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  149.  
  150. 		Matrix homeMatrix = new Matrix(readHome(readSize(in), in));
  151.  
  152. 		int number = Integer.parseInt(in.readLine());
  153. 		Size[] widgets = new Size[number];
  154. 		for (int i = 0; i < number; i++) {
  155. 			widgets[i] = readSize(in);
  156. 		}
  157.  
  158. 		TreeSet<Node> nodeSet = new TreeSet<Node>();
  159. 		for (int i = 0; i < number; i++) {
  160. 			nodeSet.add(new Node(true, widgets[i]));
  161. 		}
  162. 		for (int i = 0; i < number; i++) {
  163. 			for (int j = i + 1; j < number; j++) {
  164. 				nodeSet.add(new Node(false, widgets[i].intersect(widgets[j])));
  165. 			}
  166. 		}
  167. 		Size rootSize = new Size(1, 1);
  168. 		nodeSet.add(new Node(false, rootSize));
  169. 		List<Node> nodes = new ArrayList<Node>(nodeSet);
  170. 		for (int i = nodes.size() - 1; i >= 0; i--) {
  171. 			for (int j = i - 1; j >= 0; j--) {
  172. 				if (nodes.get(i).size.contain(nodes.get(j).size)) {
  173. 					nodes.get(j).children.add(nodes.get(i));
  174. 					break;
  175. 				}
  176. 			}
  177. 		}
  178.  
  179. 		nodes.get(0).visit(homeMatrix, rootSize);
  180.  
  181. 		for (int i = 0; i < widgets.length; i++) {
  182. 			Size widget = widgets[i];
  183. 			System.out.println(counts[widget.height][widget.width]);
  184. 		}
  185. 	}
  186.  
  187. 	Size readSize(BufferedReader in) throws Exception {
  188. 		String[] tokens = in.readLine().split(" ");
  189. 		int width = Integer.parseInt(tokens[1]);
  190. 		int height = Integer.parseInt(tokens[0]);
  191. 		return new Size(width, height);
  192. 	}
  193.  
  194. 	boolean[][] readHome(Size size, BufferedReader in) throws Exception {
  195. 		boolean[][] components = new boolean[size.height][size.width];
  196. 		for (int y = 0; y < size.height; y++) {
  197. 			String line = in.readLine();
  198. 			for (int x = 0; x < size.width; x++) {
  199. 				components[y][x] = line.charAt(x) == '1';
  200. 			}
  201. 		}
  202. 		return components;
  203. 	}
  204.  
  205. 	static void print(boolean[][] components) {
  206. 		for (int y = 0; y < components.length; y++) {
  207. 			for (int x = 0; x < components[0].length; x++) {
  208. 				char digit;
  209. 				if (components[y][x]) {
  210. 					digit = '1';
  211. 				} else {
  212. 					digit = '0';
  213. 				}
  214. 				System.out.print(digit);
  215. 			}
  216. 			System.out.println();
  217. 		}
  218. 	}
  219.  
  220. 	static void print(Node node, int spaces) {
  221. 		for (int i = 0; i < spaces; i++) {
  222. 			System.out.print(" ");
  223. 		}
  224. 		if (node.widget) {
  225. 			System.out.print("(");
  226. 		} else {
  227. 			System.out.print("[");
  228. 		}
  229. 		System.out.print(node.size.width);
  230. 		System.out.print(",");
  231. 		System.out.print(node.size.height);
  232. 		if (node.widget) {
  233. 			System.out.print(")");
  234. 		} else {
  235. 			System.out.print("]");
  236. 		}
  237. 		System.out.println();
  238. 		ListIterator<Node> iter = node.children.listIterator();
  239. 		while (iter.hasNext()) {
  240. 			print(iter.next(), spaces + 1);
  241. 		}
  242. 	}
  243. }
  244.  
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/huANAJ
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

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!