Polycarp And Love For Optics
Polycarp gave you a N * N grid with each cell either comprising of a '#' or a '.' character.
'#' denotes a blocked cell whereas '.' denotes an empty cell.
Recently, he got admission into a prestigious institute which specializes in Optics. He has a challenge to prepare for a local contest of institute. So, after days of thinking he came up with an idea. You are his good friend and have to help him solve the following problem based on his new idea.
A ray of light starts from the west direction and moves towards east. However, it cannot move through a blocked cell in the rectangular grid.
You need to place reflectors(opaque on one side, shiny on the other) in the grid to reflect light towards south such that maximum number of rays emerge out from the south.
You have solved a lot of problems related to physics in your high school but now you remember less about the laws of Optics. Hence, you decide to bring your programming knowledge to rescue. Help your friend Polycarp to solve the problem.
Note : A ray of light cannot be reflected multiple times by using multiple reflectors.
- The first line of the input contains an integer T denoting the number of test cases.
- First line of each test case contains N denoting the dimension of the grid..
- Next N line contains N characters each denoting type of characters in the grid.
- Output a single integer for each test case in a separate line, denoting the maximum number of rays that can emerge out from the south.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 500
- Grid consists of two kinds of characters only i.e '#' and '.'
Input: 1 5 ..... #..#. ..... .#... ....# Output: 4
See the image provided above for the sample test case given.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions