All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

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...
Your Rating:

Contributor

This Problem was Asked in

PayPal

Challenge Name

PayPal Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?