King of Codeland
Dom is the king of codeland. Brian, his best-friend wants to replace him. Brian wants to kill him in order to become king of codeland. Brian is standing on a rectangular grid of size n x m. The starting cell is marked 'S' and Dom is standing at cell marked with 'T', rest all the cells are marked with lowercase english alphabet (It is guaranteed that there is only one 'S' and one 'T' in the grid). The time required to move from one cell to another is 1 minute. It takes 0 minutes to move within a cell. A person can only move from a cell to it's adjacent cells (if available). A person can visit atmost 'k' different types of cell. Cells marked with 'S' and 'T' are not counted. But, a person can visit 'S' and 'T' exactly once. Brian wants to kill him as soon as possible. So, he asks for your help to kill Dom. Your task is to find a path from 'S' to 'T' that takes minimum time. If there are multiple paths taking same time, print the lexicographically smallest one.
First line consists of an integer 't' denoting number of testcases. Each testcase consists of three integers 'n', 'm' and 'k'. Then 'n' lines follows. Each line consist of exactly 'm' characters which are lowercase english alphabets and the characters 'S' and 'T'.
If there is a path sequence satisfying the above mentioned conditions print the path(don't print the characters 'S' and 'T'),else print -1. Note: If the path sequence is empty just print a blank line.
- 1<= n,m <=50
- n x m >=2/b>
Input: 3 3 5 2 SbcaT acbab acccb 1 4 1 SxyT 3 4 2 Sbbb aabT abbc Output:
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, 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