{"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 bị khóa ở ô (0, 0) trong một nhà tù hình chữ nhật được bảo vệ chặt chẽ có kích thước R x C. Anh ta phải đến cổng ở (R-1, C-1) để thoát khỏi nhà tù. Kathiresan có thể di chuyển từ bất kỳ ô nào đến bất kỳ trong 4 ô kề của nó (Bắc, Đông, Tây và Nam). Nếu Kathiresan hiện đang ở (x1, y1), thì anh ta có thể di chuyển đến (x2, y2) nếu và chỉ nếu abs(x2-x1)+abs(y2-y1) \u003d\u003d 1 và 0 \u003c\u003d x2 \u003c R và 0 \u003c\u003d y2 \u003c C\u003c/p\u003e\n\u003cp\u003eKathiresan nào đó đã có được bản đồ của nhà tù\u003c/p\u003e\n\u003cp\u003eNếu map[x1][y1] \u003d\u003d map[x2][y2] thì Kathiresan có thể di chuyển từ (x1, y1) đến (x2, y2) mà không cần giết bất kỳ lính gác nào.\u003c/p\u003e\n\u003cp\u003eNếu map[x1][y1] !\u003d map[x2][y2] thì Kathiresan có thể di chuyển từ (x1, y1) đến (x2, y2) bằng cách giết một lính gác.\u003c/p\u003e\n\u003cp\u003eCho bản đồ của nhà tù, hãy tìm số lính gác tối thiểu mà Kathiresan phải giết để thoát khỏi nhà tù.\u003c/p\u003e\n\n\u003ch3\u003eNhập vào\u003c/h3\u003e\n\u003cp\u003eDòng đầu tiên chứa một số nguyên t, số lượng bộ test. Đối với mỗi bộ test, dòng đầu tiên chứa hai số nguyên R và C đại diện cho kích thước của nhà tù hình chữ nhật theo sau là R chuỗi đại diện cho bản đồ của nhà tù hình chữ nhật.\u003c/p\u003e\n\n\u003ch3\u003eXuất ra\u003c/h3\u003e\n\u003cp\u003eĐối với mỗi bộ test, tìm số lính gác tối thiểu mà Kathiresan phải giết để thoát khỏi nhà tù.\u003c/p\u003e\n\n\u003ch3\u003eGiới hạn\u003c/h3\u003e\n\u003cp\u003e1 \u003c\u003d t \u003c\u003d 10\u003c/p\u003e\n\u003cp\u003e2 \u003c\u003d R \u003c\u003d 1000\u003c/p\u003e\n\u003cp\u003e2 \u003c\u003d C \u003c\u003d 1000\u003c/p\u003e\n\u003cp\u003e\u0027a\u0027 \u003c\u003d map[i][j] \u003c\u003d \u0027z\u0027\u003c/p\u003e\n\n\u003ch3\u003eVí dụ\u003c/h3\u003e\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"}}]}