KATHTHI - KATHTHI

给出一个$n \times m$的网格，每个位置有一个小写字母，初始在$(1, 1)$，每次可以向上下左右走，问走到$(n, m)$的最小花费 设$(x, y)$为当前位置，$(nx, ny)$为下一位置。$s[x][y]$表示$(x, y)$位置的字符。 若$s[x][y] = s[nx][ny]$，则移动的花费为$0$，否则花费为$1$ 提示：不要用某些“活着”的最短路算法 @[chen_zhe](/space/show?uid=8457)

```          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<CKathiresan 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 def6 6akacccaaacfcamdfccaokhddzyxwdpzyxwdd5 5abbbcabaccaaaccaefcicdgdd Sample Output: 0 322 ```

4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd

0
3
2
2