Sherlock and the Grid
All submissions for this problem are available.
Read problems statements in English, Mandarin Chinese and Russian as well.
Sherlock is stuck. There is a N X N grid in which some cells are empty (denoted by ‘.’), while some cells have rocks in them (denoted by ‘#’). Sherlock is on the South of the grid. He has to watch what is happening on the East of the grid. He can place a mirror at 45 degrees on an empty cell in the grid, so that he'll see what is happening on East side by reflection from the mirror.
But, if there's a rock in his line of sight, he won't be able to see what's happening on East side. For example, following image shows all possible cells in which he can place the mirror.
You have to tell Sherlock in how many possible cells he can place the mirror and see what's happening on East side.
First line, T, the number of testcases. Each testcase will consist of N in one line. Next N lines each contain N characters.
For each testcase, print the number of possible options where mirror can be placed to see on the East side.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 1000
Input: 2 3 #.. #.. #.. 3 #.# #.# #.# Output: 6 0
Example case 1. All places where rock are not there are valid positions.
Example case 2. No valid positions.
Note: Large input data. Use fast input/output.
Time limit for PYTH and PYTH 3.1.2 has been set 8s.
|Tags||cook50, darkshadows, dynamic-programming, simple|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.