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 (R-1, C-1) 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(x2-x1)+abs(y2-y1) == 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

Added by:cegprakash
Date:2015-01-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2019-07-30 11:56:37 asad
tried with [stop spoiling other people]

Last edit: 2019-09-30 14:45:33
2019-06-13 19:02:30
Learn about optimization of Dijkstra's algorithm for graphs having constrained weights.
2018-12-03 09:48:45
getting TLE again and again :(
2018-08-13 17:46:25
[spoiler] does the trick!

Last edit: 2018-08-22 15:44:51
2018-02-06 15:02:09
the last case is incorrect ! answer must be 3 . i dont understand how answer is 2?

reply by cegprakash : anurag_tangri: initially you go down. Then you can take a right at 3rd row without killing anyone and kill a guard to reach c, and then go down, kill a guard to reach d, finally take a right in the last row


Last edit: 2018-08-22 15:52:02
2018-01-23 21:52:20
don't do [spoiler], learn [spoiler]

Last edit: 2018-08-22 15:45:14
2018-01-17 15:07:46
USED [spoiler] AC in first attempt

Last edit: 2018-08-22 15:45:35
2017-06-18 20:41:49
Learnt something new in order to reduce TLE.!!
2017-04-13 23:47:42
fastio not required, hint [spoiler]

Last edit: 2017-08-02 13:15:12
2017-02-12 20:25:33
AC after 6 TLE and learnt something new..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.