Problem Link :
[Contest][1]
Difficulty: Easy-medium
Explanation
The problem can be solved by using floodfill algorithm with a simple twist. The only difference is to move more than one point in contrast to regular floodfill. Ajinkya moves in a direction until a blocking object appears; so move counter in floodfill algorithm remains same moving in four directions from a point.
The solution requires O(N^2) memory since it keeps the grid and a grid for floodfill. It requires O(N^3) time for floodfill algorithm.
/* Floodfill: O(N^3) */
// Floodfill
void floodfill()
{
mark[p[0].y][p[0].x]=1; // start from the location of first cow
queue q;
q.push(p[0]);
for ( ; ; )
{
Point pt=q.front();
q.pop();
cnt=mark[pt.y][pt.x];
for (int k=0; k<4; k++)
// Movement in one direction
// enqueue all the points until a bush appears
for (int i=pt.y+d[k][0],j=pt.x+d[k][3]; i>=0 && j>=0 && i<n &&j<m; i+=d[k][0],j+=d[k][4])
{
if (mat[i][j]=='*') break;
if (!mark[i][j])
{
mark[i][j]=cnt+1; // floodfill marker matrix
// records the minimum number of mirrors
// upto the location i,j
Point pn;
pn.y=i, pn.x=j;
q.push(pn);
}
if (i==p[1].y && j==p[1].x) return; // finish if it is second location
}
}
cout<<cnt<<endl;
}
[1]: http://codechef.com/CDCR2015/problems/CDCR15_3