hi all,
i implemented the same problem with bfs but i'm getting TLE.....plz tell
how to reduce my running time....
my code is as follows...
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int main()
{
int i,f,s,g,u,d;//f=no. of floors,s=start,g=goal,u=up,d=down
scanf("%d%d%d%d%d",&f,&s,&g,&u,&d);
if(s==g)
{
printf("0\n");
return 0;
}
vector< vector<int> > v(f+1); //v[1] represents floors reachable
from 1st floor......till v[f]
//first task is to build the graph using no. of floor,up and down
for(i=1;i<=f;i++)
{
if( (i+u)<=f )
v[i].push_back(i+u);
if( (i-d)>=1 )
v[i].push_back(i-d);
}
//graph created
//now apply bfs from start node and check if we can reach goal...if yes
then in how many steps..
queue<int> q;
vector<int> p(f+1,0); //visited flag
q.push(s); //s is the start vertex
p[s]=1;
vector<int>::iterator it;
vector<int> a(f+1,0); //array containing distances
a[s]=0;
while(!q.empty())
{
i=q.front();
//get tail element from the queue
q.pop();
for(it=v[i].begin();it!=v[i].end();it++)
{
if( *it==g )
{
printf("%d\n",a[i]+1);
return 0;
}
if(!p[*it]) //we have not visited this vertex yet
{
a[*it]=a[i]+1;
p[*it]=1;
q.push(*it);
}
}
}
printf("use the stairs\n");
return 0;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
<http://gplus.to/amolsharma99>
<http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99>
On Thu, Nov 17, 2011 at 5:48 PM, Anshul AGARWAL
<anshul.agarwa...@gmail.com>wrote:
> finally got AC,(using bfs)
> thanx DON for provide such nice test case
>
> *Anshul Agarwal
> Nit Allahabad
> Computer Science**
> *
>
>
> On Wed, Nov 16, 2011 at 8:14 PM, SAMMM <somnath.nit...@gmail.com> wrote:
>
>> U need to check for the case when (s==g) source and destination are
>> same , I got stuck here , after handling this case I got accepted :)
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
