fork download 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.HashMap;
  6.  
  7. public class Main {
  8.     public static class Widget {
  9.         public int widgetW;
  10.         public int widgetH;
  11.  
  12.         public Widget(int w, int h) {
  13.             widgetW = w;
  14.             widgetH = h;
  15.         }
  16.  
  17.         @Override
  18.         public boolean equals(Object obj) {
  19.             if (obj instanceof Widget) {
  20.                 Widget w = (Widget) obj;
  21.                 return w.widgetW == widgetW && w.widgetH == widgetH;
  22.             }
  23.             return false;
  24.         }
  25.  
  26.         @Override
  27.         public int hashCode() {
  28.             return widgetH * 65536 + widgetW;
  29.         }
  30.     }
  31.  
  32.     int[][] space;
  33.     int w, h;
  34.  
  35.     int[][] widgets;
  36.     HashMap<Widget, Integer> cache;
  37.  
  38.     public static void main(String[] args) throws IOException {
  39.         Main paizenMain = new Main();
  40.         paizenMain.run();
  41.     }
  42.  
  43.     public void run() throws IOException {
  44.         parseStdIn();
  45.  
  46.         cache = new HashMap<Main.Widget, Integer>();
  47.         for (int i = 0; i < widgets.length; i++) {
  48.             Widget widget = new Widget(widgets[i][1], widgets[i][0]);
  49.  
  50.             if (cache.containsKey(widget)) {
  51.                 System.out.println(cache.get(widget));
  52.             } else {
  53.                 int count = convolveAndCount(widgets[i]);
  54.                 cache.put(widget, count);
  55.                 System.out.println(count);
  56.             }
  57.         }
  58.     }
  59.  
  60.     private int convolveAndCount(int[] widget) {
  61.         int widgetW = widget[1];
  62.         int widgetH = widget[0];
  63.         if (w < widgetW || h < widgetH) {
  64.             return 0;
  65.         }
  66.  
  67.         int[][] space2 = new int[h - widgetH + 1][w];
  68.  
  69.         // row convolution
  70.         for (int i = 0; i < widgetH; i++) {
  71.             for (int y = 0; y < h - widgetH + 1; y++) {
  72.                 for (int x = 0; x < w; x++) {
  73.                     space2[y][x] += space[y + i][x];
  74.                 }
  75.             }
  76.         }
  77.         // // check
  78.         // for (int i = 0; i < h - widgetH + 1; i++) {
  79.         // for (int j = 0; j < w; j++) {
  80.         // System.out.print(space2[i][j]);
  81.         // }
  82.         // System.out.println();
  83.         // }
  84.         int[][] space3 = new int[h - widgetH + 1][w - widgetW + 1];
  85.  
  86.         // column convolution
  87.         for (int i = 0; i < widgetW; i++) {
  88.             for (int y = 0; y < h - widgetH + 1; y++) {
  89.                 for (int x = 0; x < w - widgetW + 1; x++) {
  90.                     space3[y][x] += space2[y][x + i];
  91.                 }
  92.             }
  93.         }
  94.  
  95.         // // check
  96.         // for (int i = 0; i < h - widgetH + 1; i++) {
  97.         // for (int j = 0; j < w - widgetW + 1; j++) {
  98.         // System.out.print(space2[i][j]);
  99.         // }
  100.         // System.out.println();
  101.         // }
  102.  
  103.         // count
  104.         int count = 0;
  105.         for (int y = 0; y < h - widgetH + 1; y++) {
  106.             for (int x = 0; x < w - widgetW + 1; x++) {
  107.                 if (space3[y][x] == 0)
  108.                     count++;
  109.             }
  110.         }
  111.         return count;
  112.     }
  113.  
  114.     private void parseStdIn() throws IOException {
  115.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  116.  
  117.         int[] size = splitStrToIntArray(br.readLine());
  118.  
  119.         h = size[0];
  120.         w = size[1];
  121.         space = new int[h][w];
  122.  
  123.         for (int i = 0; i < h; i++) {
  124.             String line = br.readLine();
  125.             for (int j = 0; j < w; j++) {
  126.                 space[i][j] = line.charAt(j) - '0';
  127.             }
  128.         }
  129.  
  130.         int widgetNum = Integer.parseInt(br.readLine());
  131.         widgets = new int[widgetNum][2];
  132.         for (int i = 0; i < widgetNum; i++) {
  133.             widgets[i] = splitStrToIntArray(br.readLine());
  134.         }
  135.  
  136.         // // check
  137.         // for (int i = 0; i < h; i++) {
  138.         // for (int j = 0; j < w; j++) {
  139.         // System.out.print(space[i][j]);
  140.         // }
  141.         // System.out.println();
  142.         // }
  143.         //
  144.         // for (int i = 0; i < widgetNum; i++) {
  145.         // System.out.println(widgets[i][0] + " " + widgets[i][1]);
  146.         // }
  147.     }
  148.  
  149.     private int[] splitStrToIntArray(String str) {
  150.         String[] strings = str.split("\\s");
  151.         int[] intArray = new int[strings.length];
  152.  
  153.         for (int i = 0; i < strings.length; i++) {
  154.             intArray[i] = Integer.parseInt(strings[i]);
  155.         }
  156.  
  157.         return intArray;
  158.     }
  159.  
  160. }
  161.  
Success #stdin #stdout 0.08s 380352KB
comments (?)
stdin 
8 30
000000100010011000000100010011
001001100001010000010001010101
000010001010101000010001001010
100000001001100000000100010011
100000001010011000010001010101
000010001001010000010001001010
110000111010101000000100010011
000010001010100000010001010100
24
2 2
2 3
3 2
2 2
2 3
3 4
4 4
3 3
2 3
4 3
300 12
53 299
1 2
4 7
3 10
10 3
2 5
4 4
8 4
2 1
8 8
8 5
1 1
6 7
7 1
4 2
2 7
4 1
1 8
3 3
4 4
5 5
2 2
3 2
3 4
stdout 
46
26
29
46
26
6
5
16
26
12
0
0
104
0
0
0
3
5
1
103
0
0
167
0
https://ideone.com/fl4oRc
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!