CDCR2015-Ajinkya And Punctuality-EDITORIAL

[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```