This is my 4th time posting this. Please help me with the part (c) only. I know

Question

This is my 4th time posting this. Please help me with the part (c) only. I know part (a) and (b) already. And please stop copying and pasting the same thing again and again for (a) and (b).

Problem 1 Starting with a map represented by a rectangular grid with height h and width w. Cells are numbered (0, 0) in the top left to (h?1, w?1) in the bottom right. Each cell in the grid is either empty or contains an impassable object. All movements on the map are done as a single step to a cell that is adjacent horizontally or vertically. No diagonal movement is permitted.

(a) Write an algorithm that uses a breadth first search to find the length of the shortest path from (0, 0) to (w ? 1, h ? 1). Return ?1 if no such path exists.

(b) What is the worst case complexity for your algorithm? Be sure to specify how the input size is measured and show your work.

(c) Modify your algorithm from part (a) to return the shortest path from (0, 0) to (w ? 1, h ? 1) in addition to its length. How does your change affect the time complexity? How does your change affect the amount of memory required.

Explanation / Answer

Written below is the C++ function which uses Breadth-First-Search to calculate "length of shortest path" (according to part (a) ) and maintains a "path" array to keep track of the parent of the visited nodes. This "path" array is actually used to print the "shortest path" between two given nodes...

void BFS(int x,int distance[],int path[])
{

list<int>q;int w; //here a Quee data structure is implemented using list (a c++ stl container)
q.push_back(x);// 'x' is the source node
distance[x]=0;

while(!(q.empty()))
{

int v=q.front();
q.pop_front();

for(int i=0;i<n;i++)
{

w=i;
if(a[v][i]!=0)
{

if(distance[w]==-1)
{
q.push_back(w);
distance[w]=distance[v]+1;
path[w]=v;
}
}
}
}

cout<<endl;
int dest;
cout<<"enter destination"<<endl;
cin>>dest;

cout<<endl<<"shortest distance is "<<distance[dest]<<endl;

cout<<endl;
vector<int>route;
int k=dest;
for(int i=0;i<n;i++)
{
route.push_back(k);

if(k==x)
{
break;
}
for(int j=0;j<n;j++)
{
if(j==k)
{
k=path[j];
break;
}
}

}
cout<<"shortest path is"<<endl;
for(int i=route.size()-1;i>=0;i--)
{
if(i==0)
cout<<route[i];
else
cout<<route[i]<<"-->";
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.