KATHTHI - KATHTHI
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.
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.
For each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.
1 <= t <= 10
2 <= R <= 1000
2 <= C <= 1000
'a' <= map[i][j] <= 'z'
[spoiler] does the trick!Last edit: 2018-08-22 15:44:51
the last case is incorrect ! answer must be 3 . i dont understand how answer is 2?
don't do [spoiler], learn [spoiler]Last edit: 2018-08-22 15:45:14
USED [spoiler] AC in first attemptLast edit: 2018-08-22 15:45:35
Learnt something new in order to reduce TLE.!!
fastio not required, hint [spoiler]Last edit: 2017-08-02 13:15:12
AC after 6 TLE and learnt something new..
<Spoiler removed> and implement :-) AC one go :-) fast IO too!Last edit: 2016-11-27 03:56:41
fastIO + [Spoiler removed] = AC!!Last edit: 2016-07-29 21:53:30
cin will give TLE in C++.