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

asad: 2019-07-30 11:56:37

tried with [stop spoiling other people]

Last edit: 2019-09-30 14:45:33
abhinav_jain02: 2019-06-13 19:02:30

Learn about optimization of Dijkstra's algorithm for graphs having constrained weights.

shivansh100: 2018-12-03 09:48:45

getting TLE again and again :(

jmr99: 2018-10-18 11:26:26

[SPOILER] *___*

Last edit: 2019-01-05 12:28:59
anirudnits: 2018-08-13 17:46:25

[spoiler] does the trick!

Last edit: 2018-08-22 15:44:51
anurag_tangri: 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
shubiks: 2018-01-23 21:52:20

don't do [spoiler], learn [spoiler]

Last edit: 2018-08-22 15:45:14
nuhash_40: 2018-01-17 15:07:46

USED [spoiler] AC in first attempt

Last edit: 2018-08-22 15:45:35

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