don't bother got AC was doing lot of extra overhead --
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 Fri, Nov 18, 2011 at 1:53 PM, Amol Sharma <amolsharm...@gmail.com> wrote: > 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.
