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
wttc:
20230126 12:46:28
[spoiler] with [spoiler] or [spoiler] gives TLE.


karelisp:
20220515 12:51:26
why am I getting TLE with O(T*N) algorithm? 

onlyerror:
20220114 09:17:29
Can anyone please share their AC code? I am getting TLE 

rushi2001:
20210609 20:43:48
Try to implement [spoilerspoiler] over dijkstra to get better time complexity . Last edit: 20220902 07:05:03 

maheshwari7778:
20210401 13:48:20
Take advantage of [spoiler] Last edit: 20230908 16:20:13 

vee_nits123:
20200813 06:40:27
AC in one goes Yayy!!


mubtasim91:
20200424 23:48:19
Can someone please review my Java submission [removed ideone link spoiler]


dkkv0000:
20200114 06:50:19
[spoiler] bfs learn it and apply it Last edit: 20200127 10:51:09 

sandeepd:
20191210 20:31:18
This is a great problem. Thanks @cegprakash! 

jitendra10099:
20191210 14:55:30
Is it possible to implement it with dynamic programming ? 
Added by:  cegprakash 
Date:  20150116 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF 