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  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  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)$.