All submissions for this problem are available.
Ravana has imprisoned Sita in Ashokavana. Ram is trying to save Sita. Ravana has added some obstacles and water bodies. Initially Ram has to collect all the gold coins on the field. He can walk on water bodies only if he has ALL the gold coins with him. If there are no coins at all, he can never walk on water. He can walk on empty cells. Find the minimum number of steps Ram will take to meet Sita.
InputTest file consists of multiple test cases. First line of each test case contains N and M which denotes the number of rows and number of columns. Next N lines contains M characters which describes the Ashokavana. Empty cells are denoted by ‘.’ Obstacles are denoted by ‘#’ Water bodies are denoted by ‘~’ Gold coins are denoted by ‘*’ Initial position of Ram is denoted by ‘R’ Position of Sita is denoted by ‘S’ (Single quotes are added for clarity) Test file ends when N=0 and M=0 (Number of test cases will not exceed 50)
OutputFor each test case, print the minimum number of steps Ram will take to reach Sita. If Ram cannot reach Sita, print -1.
Number of gold coins will not exceed 20
Input: 3 3 R.. … ..S 3 3 R.* ..~ ..S 0 0 Output: 4 4
ExplanationIn test case 1, there are no water bodies/obstacles, Hence Ram can easily reach Sita in 4 steps. In test case 2, Ram will collect the gold coin at (0,2) and hence he can easily cross the water body at (1,2).
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.