### PROBLEM LINK:

[Practice][1]

[Contest][2]

**Author:** [Lalit Kundu][3]

**Tester:** [Tasnim Imran Sunny][4]

**Editorialist:** [Devendra Agarwal][5]

### DIFFICULTY:

Easy

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

There is NxN grid, you need to find number of grid positions which follow the following rule. Emanate a light ray from the point (i,j) parallel to grid axis (i.e. one ray visits (i,x) : x >=j , and the other one visits (y,j) : y>=i ) , if both the rays reach the end i.e. (i,n) and (n,j) , then we count (i,j). β#β absorbs any light ray incident to it.

### Solution:

Letβs first come up with a solution and then we will improve itβs complexity.

For every position (i,j) we iterate in X as well as in Y axis from (i,j) and see if it is a valid position, if it is a valid position then we increment our answer.

You will quickly realise that this solution will time out. Reason : It requires time complexity O(T * (n * n) * (n)) = O(T * n^{3}) [At each iteration we do atmost O(n) traversal and we do atmost O(n*n) iterations]. Worst Case for this solution will be all characters with β.β . T is the number of test cases.

Letβs improve our approach a little.

Suppose that grid point (i,j) is a valid point then you will realise that there is no need to check the x-axis ray for (i,j+1) and similarly there is no need to check y-axis ray for (i+1,j). But does that make significant change in our complexity ? The answer to this is No. Reason : Worst case is keep β#β at the boundary. But if (i,j) is not valid , we cannot comment anything on the x-ray for (i,j+1) and similarly the y-ray for (i+1,j).

### Final Solution:

Note from above that if we separate both directions and then compute , we can save a lot of computations.

So, We make 2 arrays RayX[][] and RayY[][] , RayX*[j] is 1 if a ray from (i,j) parallel to X axis reaches the end otherwise 0. RayY*[j] is 1 if a ray from (i,j) parallel to Y axis reaches the end otherwise 0.

So , we need to find O(N^{2}) entries. Can we compute each entry in O(1) time ?

Yes , we can do so.

If we know the Solution to RayX*[j] , then can we find the solution to RayX*[j-1] ?

Yes , we can do so.

**Case 1:** If * RayX[j] is 0** , then there must be a blockade from (i,j-1) also , thus RayX*[j-1] is 0 in this case.

**Case 2:**If

** , then there is no blocade from (i,j) then we check that if we can send the light ray from (i,j-1) i.e. grid does not have β#β at (i,j-1) then we say RayX*[j-1] is 1 otherwise 0.*

*RayX*[j] is 1In short RayX*[j-1] is RayX*[j] if we can send the ray from (i,j-1).

What is the Base Case ? i.e. What is the answer to RayX*[n] ?

It is 0 or 1 depending on whether grid has β.β or β#β at that position.

Leaving the Y-axis analysis as a simple exercise for the readers.

Finally for checking if a grid point is valid you only need to check if RayX*[j] is 1 and RayY*[j] is 1.

If you are unable to get the idea , have a look at the pseudo code:

**Pseudo Code**

for(int i=1;i<=n;i++)

for(int j=n;j>=1;jβ) //starting from backwards

//For RayX*[j]

if( inp*[j] ==β.β) RayX*[j] = (j!=n)?RayX*[j+1]:1

else RayX*[j] = 0 //If you cannot start the ray from here then 0

//For RayY*[j]

if ( inp[j]* == β.β ) RayY[j]* = (j!=n)RayY[j+1]*:1*

else RayY[j] = 0

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if ( RayX*[j] == 1 && RayY*[j] == 1) sum++

return sum

### Alternate Solution :

Go from right to left and keep going until you encounter any #

Similarly go from bottom to up until you encounter any #.

Have a look at the easy pseudo code:

**Pseudo Code**

for(int j=0;j< n;j++)

int ok=1 //flag which will be zero once you get an β#β and it will be 1 otherwise

for(int i=n-1;i>=0;iβ)

if(inp*[j]==β#β) ok=0 //encountered the first β#β , set the ok variable to false

RayY*[j]=ok

for(int i = 0;i< n;i++)

int ok=1;

for(int j=n-1;j>=0;jβ)

if(inp*[j]==β#β) ok=0;

RayX*[j]=ok;

int ans=0;

for(int i=0;i< n;i++)

for(int j=1;j< n;j++)

if(RayX*[j] && RayY*[j]) ans++;

return ans

### AUTHORβS and TESTERβS SOLUTIONS:

[Authorβs solution][6]

[Testerβs solution][7]

[1]: http://www.codechef.com/problems/GRID

[2]: http://www.codechef.com/COOK50/problems/GRID

[3]: http://www.codechef.com/users/darkshadows

[4]: http://www.codechef.com/users/rustinpiece

[5]: http://www.codechef.com/users/devuy11

[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/GRID.cpp

[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/GRID.cpp