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
mkfeuhrer:
20161116 22:56:00
<Spoiler removed> and implement :) AC one go :) fast IO too! Last edit: 20161127 03:56:41 

Abhishek Jaisingh:
20160617 23:37:03
fastIO + [Spoiler removed] = AC!! Last edit: 20160729 21:53:30 

Keshav Reddy:
20151226 20:50:51
cin will give TLE in C++. 

Dhiresh:
20151225 08:27:39
Required fast I/O for Java 

LeppyR64:
20150528 20:14:52
I disagree with the requirement for fast I/O. I got AC using scanf and printf. 

Pulkit Singhal:
20150526 07:36:52
Nice Problem, But Fast I/O is required 

cegprakash:
20150226 12:37:02
@Narayanan PS: Please use spoj forum. I cannot manually check every wrong submission requests. 

psn:
20150215 20:25:20
My logic seems correct and it works fine in my machine. I get segmentation fault here. code id  13671084. Please check! Last edit: 20150215 20:26:39 
Added by:  cegprakash 
Date:  20150116 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF 