fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) throws IOException {
  6.         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  7.         PrintWriter out = new PrintWriter(System.out);
  8.         int t = Integer.parseInt(in.readLine().trim());
  9.         while (t-- > 0) {
  10.             StringTokenizer st = new StringTokenizer(in.readLine());
  11.             int n = Integer.parseInt(st.nextToken());
  12.             int m = Integer.parseInt(st.nextToken());
  13.             int k = Integer.parseInt(st.nextToken());
  14.             char[][] grid = new char[n][m];
  15.             for (int i = 0; i < n; i++) {
  16.                 grid[i] = in.readLine().toCharArray();
  17.             }
  18.             out.println(solve(n, m, k, grid));
  19.         }
  20.         out.flush();
  21.     }
  22.  
  23.     private static int solve(int n, int m, int k, char[][] g) {
  24.         boolean[] rowHasEmpty = buildRowHasEmpty(n, m, g);
  25.         boolean[] colHasEmpty = buildColHasEmpty(n, m, g);
  26.         boolean[] rowPref = buildPrefix(rowHasEmpty);
  27.         boolean[] rowSuf  = buildSuffix(rowHasEmpty);
  28.         boolean[] colPref = buildPrefix(colHasEmpty);
  29.         boolean[] colSuf  = buildSuffix(colHasEmpty);
  30.  
  31.         int ans = 0;
  32.         for (int i = 0; i < n; i++) {
  33.             for (int j = 0; j < m; j++) {
  34.                 if (g[i][j] == 'g' && isCollectable(i, j, n, m, k, rowPref, rowSuf, colPref, colSuf)) {
  35.                     ans++;
  36.                 }
  37.             }
  38.         }
  39.         return ans;
  40.     }
  41.  
  42.     private static boolean[] buildRowHasEmpty(int n, int m, char[][] g) {
  43.         boolean[] rowE = new boolean[n];
  44.         for (int i = 0; i < n; i++) {
  45.             for (int j = 0; j < m; j++) {
  46.                 if (g[i][j] == '.') { rowE[i] = true; break; }
  47.             }
  48.         }
  49.         return rowE;
  50.     }
  51.  
  52.     private static boolean[] buildColHasEmpty(int n, int m, char[][] g) {
  53.         boolean[] colE = new boolean[m];
  54.         for (int j = 0; j < m; j++) {
  55.             for (int i = 0; i < n; i++) {
  56.                 if (g[i][j] == '.') { colE[j] = true; break; }
  57.             }
  58.         }
  59.         return colE;
  60.     }
  61.  
  62.     private static boolean[] buildPrefix(boolean[] arr) {
  63.         int len = arr.length;
  64.         boolean[] pre = new boolean[len];
  65.         pre[0] = arr[0];
  66.         for (int i = 1; i < len; i++) {
  67.             pre[i] = pre[i-1] | arr[i];
  68.         }
  69.         return pre;
  70.     }
  71.  
  72.     private static boolean[] buildSuffix(boolean[] arr) {
  73.         int len = arr.length;
  74.         boolean[] suf = new boolean[len];
  75.         suf[len-1] = arr[len-1];
  76.         for (int i = len-2; i >= 0; i--) {
  77.             suf[i] = suf[i+1] | arr[i];
  78.         }
  79.         return suf;
  80.     }
  81.  
  82.     private static boolean isCollectable(int i, int j, int n, int m, int k,
  83.                                          boolean[] rowPre, boolean[] rowSuf,
  84.                                          boolean[] colPre, boolean[] colSuf) {
  85.         if (i - k >= 0 && rowPre[i - k]) return true;
  86.         if (i + k <  n && rowSuf[i + k]) return true;
  87.         if (j - k >= 0 && colPre[j - k]) return true;
  88.         if (j + k <  m && colSuf[j + k]) return true;
  89.         return false;
  90.     }
  91. }
  92.  
Success #stdin #stdout 0.1s 53036KB
comments (?)
stdin
copy 
3
2 3 1
#.#
g.g
2 3 2
#.#
g.g
3 4 2
.gg.
g..#
g##.
stdout
copy 
2
0
4
https://ideone.com/XgwHb5
language:
Java (HotSpot 12)
created:
1 day 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!