{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eKathiresan 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) \u003d\u003d 1 and 0 \u0026lt;\u003d x2 \u0026lt; R and 0 \u0026lt;\u003d y2 \u0026lt; C\u003c/p\u003e\r\n\u003cp\u003eKathiresan somehow manages to get the map of the prison\u003c/p\u003e\r\n\u003cp\u003eIf map[x1][y1] \u003d\u003d map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) without killing any guards.\u003c/p\u003e\r\n\u003cp\u003eIf map[x1][y1] !\u003d map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) by killing a guard.\u003c/p\u003e\r\n\u003cp\u003eGiven the map of the prison, find the minimum number of guards Kathiresan must kill in order to escape from the prison.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe 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.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e1 \u0026lt;\u003d t \u0026lt;\u003d 10\u003c/p\u003e\r\n\u003cp\u003e2 \u0026lt;\u003d R \u0026lt;\u003d 1000\u003c/p\u003e\r\n\u003cp\u003e2 \u0026lt;\u003d C \u0026lt;\u003d 1000\u003c/p\u003e\r\n\u003cp\u003e\u0027a\u0027 \u0026lt;\u003d map[i][j] \u0026lt;\u003d \u0027z\u0027\u003c/p\u003e\r\n\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n2 2\r\naa\r\naa\r\n2 3\r\nabc\r\ndef\r\n6 6\r\nakaccc\r\naaacfc\r\namdfcc\r\naokhdd\r\nzyxwdp\r\nzyxwdd\r\n5 5\r\nabbbc\r\nabacc\r\naaacc\r\naefci\r\ncdgdd\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n3\r\n2\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}