KATHTHI  KATHTHI
Kathiresan is initially locked at cell (0, 0) in a highly guarded rectangular prison of order R x C. He must reach the gate at (R1, C1) in order to escape from the prison. Kathiresan can move from any cell, to any of its 4 adjacent cells (North, East, West and South). If Kathiresan is currently at (x1, y1), then he can move to (x2, y2) if and only if abs(x2x1)+abs(y2y1) == 1 and 0 <= x2 < R and 0 <= y2 < C
Kathiresan somehow manages to get the map of the prison
If map[x1][y1] == map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) without killing any guards.
If map[x1][y1] != map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) by killing a guard.
Given the map of the prison, find the minimum number of guards Kathiresan must kill in order to escape from the prison.
Input
The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers R and C representing the order of the rectangular prison followed by R strings representing the map of the rectangular prison.
Output
For each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.
Constraints
1 <= t <= 10
2 <= R <= 1000
2 <= C <= 1000
'a' <= map[i][j] <= 'z'
Sample
Input: 4 2 2 aa aa 2 3 abc def 6 6 akaccc aaacfc amdfcc aokhdd zyxwdp zyxwdd 5 5 abbbc abacc aaacc aefci cdgdd Output: 0 3 2 2
hide comments
asad:
20190730 11:56:37
tried with [stop spoiling other people] Last edit: 20190930 14:45:33 

abhinav_jain02:
20190613 19:02:30
Learn about optimization of Dijkstra's algorithm for graphs having constrained weights. 

shivansh100:
20181203 09:48:45
getting TLE again and again :( 

anirudnits:
20180813 17:46:25
[spoiler] does the trick! Last edit: 20180822 15:44:51 

anurag_tangri:
20180206 15:02:09
the last case is incorrect ! answer must be 3 . i dont understand how answer is 2?


shubiks:
20180123 21:52:20
don't do [spoiler], learn [spoiler] Last edit: 20180822 15:45:14 

nuhash_40:
20180117 15:07:46
USED [spoiler] AC in first attempt Last edit: 20180822 15:45:35 

sas1905:
20170618 20:41:49
Learnt something new in order to reduce TLE.!! 

gboduljak:
20170413 23:47:42
fastio not required, hint [spoiler] Last edit: 20170802 13:15:12 

vengatesh15:
20170212 20:25:33
AC after 6 TLE and learnt something new.. 
Added by:  cegprakash 
Date:  20150116 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF 