DCEPCA02 - Ant Colony Optimization

Ants are known to move in groups and in perfect order. However, in our problem the ants can move only in directions Left (L), Right (R), Up (U), Down (D). The place is a rectangular grid. There are 2 types of ants: Type A and Type B. Each ant type has its own queen ant which defines the 2 directions at which their type of ants can reproduce ants.

A starting cell is given where one ant of each type is standing (A and B). When the process begins, each type of ant produces 4 ants, 2 ants of their type in the 2 directions (1 ant per direction) specified by their queen ant and 2 ants of the other type in the remaining 2 directions. So if queen ant of type A says LR and queen ant of type B says UD then A ant produces new type A ants at left cell and right cell and new type B ants at up cell and down cell of the original cell. Similarly, type B ant produces 2 new type A ants in left and right cell and 2 new type B ants in up cell and down cell. The ants produced again reproduce more ants at their adjacent cells according to the same directions given by the their queen ant.

Reproducing ants at adjacent cells take 1 time unit. You need to find the sum of the minimum time in which type A ant reaches the end point and the minimum time in which type B ant reaches the end point. If any type of ant cannot reach end point, the answer is -1.

Constraints

T ≤ 10
0 < M ≤ 500
0 < N ≤ 500
0 ≤ SX, EX < M
0 ≤ SY, EY < N

Input

T denotes the number of test cases. Each test case consists of 4 lines. The first line gives M and N which is the size of the grid. The second line gives starting cell cordinates SX and SY. The third line gives end point cell cordinates EX and EY. The fourth line gives a permutation of LRUD denoting the directions provided by queen ant to move. The first two characters of the string gives the directions of queen ant type A and last two characters gives direction of queen ant type B.

Output

Print T lines each giving the minimum time in which ant of both types can reach the ending cell for each testcase ie. Find sum of (minimum time at which A type ant reaches end point + minimum time at which B type ant reaches end point.)

Example

Input:
3
5 5
1 1
3 4
LRUD
2 4
0 2
0 3
RULD
2 4
0 2
1 1
URDL

Output:
10
-1
6

Explanation

Test Case 1: Minimum time at which a type A ant reaches end point = 5, and minimum time at which a type B ant reaches end point = 5

Test Case 2: B cannot reach end point. Hence answer is -1.

Test Case 3: Minimum time at which a type A ant reaches end point = 4, and minimum time at which a type B ant reaches end point = 2


Added by:dce coders
Date:2012-12-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem

hide comments
2016-06-20 10:27:20
Numbering columns left to right 0 through N-1 and rows top to bottom 0 through M-1, moving 'up' from (x,y) -> (x-1,y), 'down' = (x+1,y), 'left' = (x,y-1), 'right' = (x,y+1).
2015-06-07 11:51:04 ashok choudhary
problem statement is not clear. Test cases are not helpful @dce coders.
2013-04-26 02:14:20 Andy Y.F. Huang
Moving UP from (x,y) is (x,y-1) and moving DOWN from (x,y) is (x,y+1).
I got AC assuming this.
2013-01-02 15:28:43 (Tjandra Satria Gunawan)(曾毅昆)
Can anyone explain why "TestCase 2: B cannot reach endpoint. Hence answer is -1"?
2012-12-11 15:53:56 Ehor Nechiporenko
@Aman, the same as in my algo.
Seems we misunderstood the condition. But which is correct? I don't know(
2012-12-11 15:05:37 Aman Gupta
Ok, someone please tell me how the answer for Minimum point at which type A ant can reach the endpoint is 4, isn't it 2? 0,2 (A) -> 0,1 (B) -> 1,1(A) , or have I understood the question wrong
2012-12-09 20:56:16 Ehor Nechiporenko
I misunderstood the problem. Could you clarify it. On my algo, for second test:
1) Ant A produes Ant A to Right direction to point (1, 2)
2) Ant A from point (1,2) produces Ant of type A in UP direction to point (1,3)
3) Ant A from point (1,3) produces Ant of type B in LEFT direction to point (0, 3)
Could you please tell, where am I wrong?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.