GRID - editorial

editorial
, , ,
21

No need for dynamic programming in this question. Just throw light from east and then from south.
Indexes which recieved light from both east and south will have count 2. Rest will have count 0(initial) or 1(just from 1 side). Blocks are numbered 99.

While throwing light if you occur a 99/block stop the light else continue in that row or column.

At end count all blocks with count==2 and that is the answer. :slight_smile:

22

here is my solution for the above problem in cpp
https://github.com/anjn98/codechef/blob/master/GRID.cpp

23

My approach was:

  1. Make two NxN arrays
    1. Vertical array (to trace visibility from east)
    2. Horizontal array (to trace visibility from south)
  2. iterate each row from right to left in horizontal array. Mark items which are not visible.
  3. iterate each row from bottom to top in horizontal array and element is called v[i][j]. If v[i][j]=='.' and h[i][j]=='.' then Its a match :)
**Example**: Same example which is given in figure of problem description

Step 1: Horizontal array initially be like

…#…

…#

…

.##.#

…#.

Vertical array initially be like

…#…

…#

…

.##.#

…#.

Step 2:
Horizontal array be like
###…

…

####.

As I cannot see beyond a stone from east

Vertical array be like

…#…

…#

…

.##.#

…#.

Step 3:
Horizontal array be like

###…

…

####.

Vertical array be like

.####

.####

.####

.####

…#.

As I cannot see beyond a stone from south

Step 4: Answer will be the count of points which are common in both as ‘.’ Hence answer is 2

My JAVA solution is can be found HERE