### 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[i][j] is 1 if a ray from (i,j) parallel to X axis reaches the end otherwise 0. RayY[i][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[i][j] , then can we find the solution to RayX[i][j-1] ?

Yes , we can do so.

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

**Case 2:** If **RayX[i][j] is 1** , 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[i][j-1] is 1 otherwise 0.

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

What is the Base Case ? i.e. What is the answer to RayX[i][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[i][j] is 1 and RayY[i][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[i][j]
if( inp[i][j] =='.') RayX[i][j] = (j!=n)?RayX[i][j+1]:1
else RayX[i][j] = 0 //If you cannot start the ray from here then 0
//For RayY[i][j]
if ( inp[j][i] == '.' ) RayY[j][i] = (j!=n)RayY[j+1][i]:1
else RayY[j][i] = 0
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if ( RayX[i][j] == 1 && RayY[i][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[i][j]=='#') ok=0 //encountered the first '#' , set the ok variable to false
RayY[i][j]=ok
for(int i = 0;i< n;i++)
int ok=1;
for(int j=n-1;j>=0;j--)
if(inp[i][j]=='#') ok=0;
RayX[i][j]=ok;
int ans=0;
for(int i=0;i< n;i++)
for(int j=1;j< n;j++)
if(RayX[i][j] && RayY[i][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