program for this question

See more:

Perl

Python

Jack is very fond of his girlfriend, Jilly. He is ready to go M miles to meet Jilly, and he

knows Jilly loves surprises. So, he decides to pick up some goodies for her on his way

and sets out on this journey with R rupees in his wallet.

On his way, Jack finds shops of four types. The shops along with the minimum cost of

each item is given below:

Dresses - Rs. 2000

Shoes - Rs.1000

Chocolates - Rs.500

Flowers - Rs.500

Jack wants to give Jilly as many gifts as possible, so he is reluctant to spend more

than the minimum amount at each shop and he would prefer to buy two different

items of the same cost rather than spend the lot on buying more of the same item.

Given a map from Jack's location to Jilly's, you are asked to help Jack decide which

way to go, such that he can pick up maximum number of goodies for Jilly and get to

her as fast as possible.

Input :

The first line of input denotes the number of testcases T. The first line of each

testcase has two space-separated values R and M. The second line defines the

matrix NxM which represents the map. The following N lines define the 2D array

which represents the map from Jack's location to Jilly's. Dresses are represented

by D, Shoes by S, Choloates by C and Flowers by F; Jack by J and Jilly by G.

Assume that moving from one block on the map to its adjacent block covers a

distance of 1 mile.

Output :

The first line of output should represent the number of miles that Jack has

travelled. The second line follows to display all the different blocks that he visited

as shown in the sample output. Print -1 if it is not possible for Jack to meet Jilly.

Confidential: rapidBizApps Screening Problem-Set.

Do not share/distribute without prior written approval from rapidBizApps

Sample Input :

2

3000 10

5 7

J # # # # # #

# # D1 # C1 # #

# # # # # # G

# # C2 # # F1 #

# # # # # # #

Sample Output :

10

J # # # # # #

| - D1 # C1 # #

# # | # # # G

# # C2 - - F1 |

# # # # # # #