FROGGER  FROGGER
“Frogger” was one of the first really popular arcade games after it was introduced by SEGA in 1981. The game consists of helping a frog cross a multilane motorway without getting run over by a car. You are given a view of an nlane motorway where each lane consists of m different spaces that can either be empty or be occupied by a car. On each side of the motorway is a curb on which the frog can move freely. In the traffic lanes the frog can only move on the spaces not occupied by cars. The motorway is constructed in such a way that the direction in which the cars travel alternates between the lanes, with cars in the first lane (the one closest to the starting point of the frog) moving to the right. The cars never switch lanes and only move one step forward in each turn. To ensure a steady supply of traffic, a car that reaches the boundary of its lane is reentered at the opposite end of its lane. In one turn of the game all the cars move one step in their assigned direction while the frog can either move one step to the right or to the left, or one step up or down (between lanes or between the curb and the adjoining lane), or it can stand still. Contrary to the cars the frog cannot “wraparound” i.e. move in one step between the first and last position of a lane or a curb. The frog and the cars move simultaneously. Thus the frog can move to a space given that there will be no car on it in the next round. If the frog is on the same space at the same time as a car it is run over and dies. Note that the frog can jump over an adjacent approaching car in the same lane as itself. Your job is to write a computer program that will calculate the minimum number of turns needed for the frog to get from its starting position on the curb to its final position on the curb on the other side of the road or to determine that this is not possible within a given number of rounds.
Input
First there will be a line containing the number of scenarios you are asked to help the frog in. For each scenario there will first be a line containing a positive integer x <= 10^5 giving the maximum number of rounds that can be used. The next line contains the number of lanes n, 1 <= n <= 20, and the length of each lane m, 1 <= m <= 50. Each of the next n + 2 lines will contain a string of m characters. The character X indicates a car, the character O (letter O) indicates a free space, the character F gives the starting position of the frog, and the character G gives the final destination of the frog. The first line indicates the destination curb, consisting of O’s and exactly one G while the last line gives the starting curb consisting of O’s and exactly one F, while the intermediate lines each represent one lane of the motorway.
Output
The output will be one line per scenario, either giving the minimum number of turns needed before the frog can get from its starting position to the final position without getting run over by a car or a statement indicating that this was not possible within the maximum number of allowed turns.
Example
Input: 2 10 4 4 OOGO XXOO XOOX XXOO XXOO OOFO 2 2 2 OG XX OO FO Output: The minimum number of turns is 9. The problem has no solution.
hide comments
shubham_001:
20170705 10:03:58
Do CHMAZE first this will be cakewalk


Jens Stimpfle:
20150222 19:32:16
Petar Bosnjak, they have been migrating the evaluation cluster from Pyramid (Pentium III) to the newer Cubes (Pentium G860) in the last months. That's a good 10 years between them, so submissions run now considerably faster.


Petar Bosnjak:
20141206 00:24:11
Array constraints are not true , I had to put 100*100 in order to get AC!


Jens Stimpfle:
20140920 19:30:03
For an optimization, think about locality properties of the graph (neighbours). Actually you don't even need to maintain an explicit cost for visited nodes. Roll your own simple data structure  minheaps are not the best choice. 

Hussain Kara Fallah:
20131118 08:10:59
can the frog stand in his place for a turn or more?! 

Ashutosh Singla:
20130922 14:33:15
Note that the frog can jump over an adjacent approaching car in the same lane as itself. what does this mean ? 

Ashish Khurange:
20100213 06:27:29
> "Note that the frog can jump over an adjacent approaching car in the same lane as itself."

Added by:  Fabio Avellaneda 
Date:  20090301 
Time limit:  8.076s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  I maratÃ³n interuniversitaria del circuito Redis  Acis. Sedes: PolitÃ©cnico  Javeriana 