## KATHTHI - KATHTHI

no tags

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
```

hide comments
 < Previous 1 2 3 Next > wttc: 2023-01-26 12:46:28 [spoiler] with [spoiler] or [spoiler] gives TLE. Try considering the fact that weights are [spoiler]. Last edit: 2023-09-08 16:19:03 karelisp: 2022-05-15 12:51:26 why am I getting TLE with O(T*N) algorithm? onlyerror: 2022-01-14 09:17:29 Can anyone please share their AC code? I am getting TLE rushi2001: 2021-06-09 20:43:48 Try to implement [spoiler-spoiler] over dijkstra to get better time complexity . Last edit: 2022-09-02 07:05:03 maheshwari7778: 2021-04-01 13:48:20 Take advantage of [spoiler] Last edit: 2023-09-08 16:20:13 vee_nits123: 2020-08-13 06:40:27 AC in one goes Yayy!! [spoiler] rocks... if map[x1][y1] != map[x2][y2] consider [spoiler] else [spoiler] Last edit: 2023-09-08 16:20:49 mubtasim91: 2020-04-24 23:48:19 Can someone please review my Java submission [removed ideone link spoiler] I am getting TLE. Last edit: 2023-09-08 16:21:32 dkkv0000: 2020-01-14 06:50:19 [spoiler] bfs learn it and apply it Last edit: 2020-01-27 10:51:09 sandeepd: 2019-12-10 20:31:18 This is a great problem. Thanks @cegprakash! jitendra10099: 2019-12-10 14:55:30 Is it possible to implement it with dynamic programming ?

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