{"code":"olp4ck2d","name":"Trò chơi chặn đường","description":"Một trò chơi trí tuệ khác mà Đan đã làm là trò chơi chặn đường. Trò chơi diễn ra trên một mê cung được biểu diễn bằng lưới ô vuông kích thước $m \\times n$, các hàng của lưới được đánh số từ $1$ đến $m$, các cột của lưới được đánh số từ $1$ đến $n$, ô nằm giao giữa hàng $i$ và cột $j$ được gọi là ô $(i, j)$. Mỗi ô có thể là ô cấm (ô không được phép đi vào) hoặc là ô tự do (ô có thể đi vào). Một tên cướp đang ở ô $(1, 1)$ và cần di chuyển đến ô $(m, n)$, mỗi bước tên cướp có thể di chuyển sang một trong bốn ô chung cạnh là ô tự do. Nhiệm vụ của người chơi là cần đặt cảnh sát vào một số ô tự do để chặn đường không cho tên cướp đi được đến ô $(m, n)$, tên cướp không thể di chuyển vào ô có cảnh sát. Biết rằng có một số ô tự do có thể đặt cảnh sát, ví dụ nếu ô $(i, j)$ là ô có thể đặt cảnh sát thì sẽ mất chi phí $c_{ij}$ $(1 \\leq c_{ij} \\leq 9)$.\r\n\r\n**Yêu cầu:** Tính chi phí ít nhất để chặn được tên cướp không di chuyển được đến ô $(m, n)$. \r\n\r\n## Input \r\n- Dòng đầu chứa hai số nguyên dương $m, n$ $(m \\times n > 1)$\r\n- Dòng thứ $i$ $(1 \\leq i \\leq m)$ trong dòng $m$ sau, mỗi dòng chứa một xâu độ dài $n$ , kí tự thứ $j$ $(1 \\leq j \\leq n)$ chỉ gồm các loại kí tự sau:\r\n    + Kí tự `#` mô tả ô tả ô là ô cấm.\r\n    + Kí tự `1` đến `9` mô tả ô là ô tự do và có thể đặt cảnh sát với chi phí tương ứng từ $1$ đến $9$.\r\n    + Kí tự `.` mô tả ô là ô tự do và không được phép đặt cảnh sát.\r\n\r\nChú ý rằng ô $(1, 1)$ và ô $(m, n)$ luôn là ô tự do không được đặt cảnh sát.\r\n\r\n## Output\r\n- Gồm một dòng chứa một số nguyên là chi phí ít nhất để đặt cảnh sát nhằm chặn tên cướp không di chuyển được đến ô $(m, n)$, nếu không tồn tại ghi $-1$.\r\n\r\n## Scoring\r\n- Subtask $1$ ($30\\%$ số điểm): $m \\leq 2; n \\leq 1000$.\r\n- Subtask $2$ ($40\\%$ số điểm): $m \\times n \\leq 2 \\times 10^{3}$.\r\n- Subtask $3$ ($30\\%$ số điểm): $m \\times n \\leq 2 \\times 10^{5}$.\r\n\r\n## Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 4\r\n        .#.1\r\n        ..2.\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 4\r\n        ....\r\n        ..1.\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        -1\r\n        ```","points":2100.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}