KATHTHI - KATHTHI

no tags 

         Kathiresan is initially locked at cell (0,0) in a highly guarded rectangular prison of order RxC. 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 it's 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.

 

Input 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

 

Sample Output:

0

3

2

2


hide comments
nuhash_40: 2018-01-17 15:07:46

USED [spoiler] AC in first attempt

Last edit: 2018-08-22 15:45:35
sas1905: 2017-06-18 20:41:49

Learnt something new in order to reduce TLE.!!

gboduljak: 2017-04-13 23:47:42

fastio not required, hint [spoiler]

Last edit: 2017-08-02 13:15:12
vengatesh15: 2017-02-12 20:25:33

AC after 6 TLE and learnt something new..

mkfeuhrer: 2016-11-16 22:56:00

<Spoiler removed> and implement :-) AC one go :-) fast IO too!

Last edit: 2016-11-27 03:56:41
Abhishek Jaisingh: 2016-06-17 23:37:03

fastIO + [Spoiler removed] = AC!!

Last edit: 2016-07-29 21:53:30
Keshav Reddy: 2015-12-26 20:50:51

cin will give TLE in C++.

Dhiresh: 2015-12-25 08:27:39

Required fast I/O for Java

LeppyR64: 2015-05-28 20:14:52

I disagree with the requirement for fast I/O. I got AC using scanf and printf.

Pulkit Singhal: 2015-05-26 07:36:52

Nice Problem, But Fast I/O is required


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