An inefficient but working method is the brute force one. Do a recursive test for all the cases possible and if you find one which helps the frog cross the road, then that is it.
Let int car_times[numLanes] store the time each car will take to reach the path where the frog is crossing the road. Frog has 3 commands at his disposal: a) jump_fwd b) jump_back c) wait Let Vector <command> cmds be the desired sequence of commands to reach the destination. We need to write a function which will produce the above global vector as its output. enum command {F, B, W}; Vector <command> cmds; int car_times[numLanes]; //given in the beginning bool try_remaining_path (int lane_num, int time_passed) { int orig_time = time_passed; int orig_lanes = lane_num; while (car_times[lane_num] - time_passed>= 1) { cmds.push_back (F); bool rest_is_possible = try_remaining_path (time_passed+1, lane_num+1); if (rest_is_possible) return true; cmds.pop(); cmds.push_back (W); time_passed++; } // if we come here, means that there was no point // in waiting in this lane_num, as the frog will be // killed at one point or the other. // let us try by jumping back one step. time_passed = orig_time; while (lane_num > 0) { cmds.push_back (B); time_passed++; lane_num--; bool rest_is_possible = try_remaining_path (time_passed, lane_num); if (rest_is_possible) return true; } // Nothing is possible in this lane. // Empty the commands B from the vector and try something else. while (orig_lanes > 0 ) { cmds.pop(); orig_lanes--; } return false; } Above seems very inefficient to me because it calculates all the possible jumps at each lane. Please help in improving it. On Jul 15, 9:24 am, Ashish kumar Jain <akjlucky4...@gmail.com> wrote: > I think this will help: > > http://en.wikipedia.org/wiki/Frogger > > Consider the roads to be n-laned and of constant width with constant time > traffic coming on each lane.For example,say after 1 minute,a car comes on > each lane but in a arithmetic sequence and not all at same time.To make it > more clear, > > at t=1 minute,car at lane 1 travelling with constant velocity v and takes > "T" time to cross the screen/lane1. > > at t=2 minute,another car comes now in lane 2 with same constant velocity > and so on.......... > > Now the frog can cross one lane either back or forth in one jump.These are > the only movements allowed.The jump time is considerable(say in above case 1 > minute only).Note that times are all not correctly mentioned and consider > times which are appropriate for the problem.The time details are mentioned > to make everyone understand the problem. > > Design an algorithm to guarantee that the frog crosses the road safely. > > Think first..........................Hint is > downwards......................... > . > . > . > . > . > . > . > . > . > . > . > . > .. > . > . > . > . > . > . > . > . > . > . > . > . > > Hint: Think in terms of multithreading,semaphores,mutex and vectors > etc.......... > > > > > > On Wed, Jul 14, 2010 at 11:33 PM, Tech Id <tech.login....@gmail.com> wrote: > > A frog has to cross a road to meet > > its beloved she-frog at the other end. > > > The road however has cars coming and > > can crush the frog. > > > Road is two lanes wide. > > > Devise an algorithm to help the frog carry on its family. > > > (I am sorry but it seems that I have missed > > some parts of the problem here. If someone > > remembers the complete question, please help me). > > Thanks in advance! > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards, > Ashish -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.