Bob and Forest
Tag(s):

## Algorithms, Binary search algorithm, Dynamic Programming, Medium, String, String, Two dimensional, dynamic programming, implementation, strings

Problem
Editorial
Analytics

You are given a 2D character array denoting forest of length N and breadth M . In the matrix, '.' denotes barren land and ' * ' denotes tree.
You are given Q questions. In each question, you are given integer K and you have to determine the number of unique squares of side less than or equal to K which contain only trees.

Input

First line : N and M (N denoting number of rows and M denoting number of columns).

Each of the next N lines contains string of M length containing '.' and '*' .

Next line consists of an integer Q, denoting number of questions.

Each of the next Q lines contains a single integer K.

Input Constraints

$1 \le N, M \le 1000$
$1 \le Q \le 10^5$
$0 \le K \le 10^3$

Output

For each question, print the number of unique squares of side less than or equal to K which contain only trees. Answer for each question should come in a new line.

SAMPLE INPUT
4 4
*..*
.***
****
.***
3
1
2
3

SAMPLE OUTPUT
12
16
17
Explanation

In the given sample , as we can see :-

Squares of side 1 containing only trees :- 12.
Squares of side 2 containing only trees :- 4.
Squares of side 2 containing only trees :- 1.

Thus answer for query 1 is 12.
Answer for query 2 i.e squares of side less than or equal to 2 are 12+4 = 16.
Answer for query 3 i.e squares of side less than or equal to 3 are 12+4+1=17.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

PayPal Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
Уведомления

?