All submissions for this problem are available.
A Government of merryland is planning to power the city.
The city is divided into AxB blocks, each block has either house(H), transformer(T) or empty land(E). The wiring to a block can be done only if the block is vertically or horizontally adjacent to a wired block. The wiring to an empty block is not done as there are no houses there. The cost of providing electricity to a particular block in the city is equivalent to the distance of block from nearest wired transformer. The distance is measured in either horizontal or vertical manner through already wired blocks. The wiring must ensure that all the blocks get the electricity, and also should ensure that the cost is minimum for wiring the city. Assume that the power enters the city from top left block and that block also has a transformer.
Assume that it is possible to provide electricity to the whole city i.e. there is atleast one way to wire the whole merryland.
1st line is number of test cases
1st line of each test cases gives values of A and B
1st line of each test case is followed by AxB matrix containing T(transformer), H(houses), E(empty region) (there are no spaces in between)
Minimum cost that the government have to bear to power whole city.
Input: 1 2 2 TH TE Output: 2
Expaination : 1 to connect T(top left corner) to H and other 1 to connect T to T)
|Time Limit:||0.314961 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.