CDCR2015-Ajinkya And Punctuality-EDITORIAL

Problem Link :


Difficulty: Easy-medium


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;

	for ( ; ; )
		Point pt=q.front();
		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;
				if (i==p[1].y && j==p[1].x) return;	// finish if it is second location