codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1461B.md (2469B)


      1 Source: https://codeforces.com/problemset/problem/1461/B
      2 
      3 B. Find the Spruce
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Holidays are coming up really soon. Rick realized that it's time to think about buying a traditional spruce tree. But Rick doesn't want real trees to get hurt so he decided to find some in an $n \times m$ matrix consisting of "*" and ".".
     22 
     23  ![](https://espresso.codeforces.com/da2453601cf083c0bb8040496806e7769bacbd2a.png) 
     24 
     25 To find every spruce first let's define what a spruce in the matrix is. A set of matrix cells is called a spruce of height $k$ with origin at point $(x, y)$ if:
     26 
     27 * All cells in the set contain an "*".
     28 * For each $1 \le i \le k$ all cells with the row number $x+i-1$ and columns in range $[y - i + 1, y + i - 1]$ must be a part of the set. All other cells cannot belong to the set.
     29 
     30 Examples of correct and incorrect spruce trees:
     31 
     32  ![](https://espresso.codeforces.com/c6d382429ea6cbc6c8c0cde9819a0d98cc9c2a9f.png) 
     33 
     34 Now Rick wants to know how many spruces his $n \times m$ matrix contains. Help Rick solve this problem.
     35 
     36 Input
     37 
     38 Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$).
     39 
     40 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 500$) — matrix size.
     41 
     42 Next $n$ lines of each test case contain $m$ characters $c_{i, j}$ — matrix contents. It is guaranteed that $c_{i, j}$ is either a "." or an "*".
     43 
     44 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $500^2$ ($\sum n \cdot m \le 500^2$).
     45 
     46 Output
     47 
     48 For each test case, print single integer — the total number of spruces in the matrix.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 4
     56 2 3
     57 .*.
     58 ***
     59 2 3
     60 .*.
     61 **.
     62 4 5
     63 .***.
     64 *****
     65 *****
     66 *.*.*
     67 5 7
     68 ..*.*..
     69 .*****.
     70 *******
     71 .*****.
     72 ..*.*..
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 5
     79 3
     80 23
     81 34
     82 ```
     83 
     84 Note
     85 
     86 In the first test case the first spruce of height $2$ has its origin at point $(1, 2)$, the second spruce of height $1$ has its origin at point $(1, 2)$, the third spruce of height $1$ has its origin at point $(2, 1)$, the fourth spruce of height $1$ has its origin at point $(2, 2)$, the fifth spruce of height $1$ has its origin at point $(2, 3)$.
     87 
     88 In the second test case the first spruce of height $1$ has its origin at point $(1, 2)$, the second spruce of height $1$ has its origin at point $(2, 1)$, the third spruce of height $1$ has its origin at point $(2, 2)$.