FROGGER - FROGGER

no tags 

“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 multi-lane motorway without getting run over by a car. You are given a view of an n-lane 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 “wrap-around” 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: 2017-07-05 10:03:58

Do CHMAZE first this will be cakewalk

Jens Stimpfle: 2015-02-22 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.

Probably time limits haven't been adapted, but personally I don't mind time limits.

Most of the old problems are now pointless because naive algorithms are sufficient for 0.00s time. And nothing can be done. While the number of testcases could be increased for most problems without breaking too much valid solutions, the individual test cases' sizes couldn't. The problems were originally thought out for ca. Pentium III hardware. On the newer hardware, even optimized I/O will be the bottleneck.

Assuming that the reason for the migration is that the Pentium III's were dying, IMO the better solution would have been to just lock these problems away.

Petar Bosnjak: 2014-12-06 00:24:11

Array constraints are not true , I had to put 100*100 in order to get AC!
Also time limit is too big...

Last edit: 2014-12-06 00:28:19
Jens Stimpfle: 2014-09-20 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: 2013-11-18 08:10:59

can the frog stand in his place for a turn or more?!

Ashutosh Singla: 2013-09-22 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: 2010-02-13 06:27:29

> "Note that the frog can jump over an adjacent approaching car in the same lane as itself."

For me this sentence was bit misleading, I concluded it as the frog can exchange position with approaching car. Just remember that under no condition: *Frog and a Car can be in same location*


Added by:Fabio Avellaneda
Date:2009-03-01
Time limit:8.076s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:I maratón interuniversitaria del circuito Redis - Acis. Sedes: Politécnico - Javeriana