A Research team want to establish a research center in a region where they found some rare-elements.They want to make it closest to all the rare-elements as close as possible so that they can reduce overall cost of research over there.It is given that all the rare-element’s location is connected by roads.It is also given that Research Center can only be build on road.Team decided to assign this task to a coder.If you feel you have that much potential…Here is the Task :- Find the shortest of the longest distance of research center from given locations of rare-elements.
locations are given in the matrix cell form where 1 represents roads and 0 no road…
number of rare-element and their location was also given(number<=5)
and order of square matrix was less than equal to (20).
while(!q.empty())
{
C c=q.front();
q.pop();
int a=c.x;
int b=c.y;
int d=c.dis;
ans[a][b]=d;
for(int i=0;i<4;i++)
{
int nx=a+xa[i];
int ny=b+yb[i];
if(issafe(nx,ny))
{
visited[nx][ny]=1;
in.x=nx;
in.y=ny;
in.dis=d+1;
q.push(in);
}
}
}
If I understand correctly, you are running a bfs from each possible cell until you reach all the destinations? That should work within the time limit since total cells is at most 20.
Yes, actually. You want to calculate the distance to each destination for each cell, so you are running a bfs from each cell. But you can do the opposite and run a bfs from each destination instead. Here you will need at most 5 bfs.