{"code":"escape","name":"Giải thoát","description":"Một thiết bị thăm dò điều khiển từ xa được thả xuống khảo sát mặt đáy của một bể hóa chất hình chữ nhật kích thước $n×m$ ô vuông. Thiết bị có thể được điều khiển để đi từ một ô sang ô kề cạnh. Trục chuyển động theo chiều ngang (sang ô cùng hàng) được kết nối với thiết bị làm lạnh, cứ mỗi lần di chuyển sang ô kề cạnh cùng hàng nhiệt độ bên trong thiết bị giảm đi $1$. Trục chuyển động theo chiều dọc (sang ô cùng cột) được gắn với thiết bị làm nóng, cứ mỗi lần di chuyển sang ô kề cạnh cùng cột nhiệt độ bên trong thiết bị tăng thêm $1$.\r\n\r\nSau khi hoàn thành nhiệm vụ khảo sát thiết bị đang ở ô được đánh dấu là `s`. Thật không may ống hút đưa thiết bị lên trên bị kẹt và chỉ có thể thu hồi thiết bị khảo sát nếu nó ở ô được đánh dấu `f`. Ngoài ra, khi đưa lên thiết bị cần có nhiệt độ gần 0 nhất có thể.\r\n\r\nTình trạng đáy của bể hóa chất được xác định bởi bản đồ $B$ kích thước $n×m$. $B_{i,j}$ được đánh dấu `.` nếu là ô trống và thiết bị thăm dò có thể đi qua. Nếu ô ($i, j$) có vật cản, không thể đi vào thì $B_{i,j}$ được đánh dấu là `#`. Tồn tại một ô được đánh dấu `s` và một ô khác – đánh dấu `f`.\r\n\r\nHãy xác định chênh lệch nhiệt độ tối thiểu (so với $0$) thiết bị thăm dò có thể đạt được khi thoát ra khỏi bể.\r\n\r\n<h4>Input</h4>\r\n\r\n- Dòng đầu tiên chứa 2 số nguyên $n$ và $m$ ($1 \\le  n, m \\le  1000$),\r\n- Dòng thứ $i$ trong $n$ dòng sau chứa xâu độ dài $m$ chứa các ký tự đã nêu, mô tả dòng thứ $i$ của bản đồ $B$.\r\n\r\n<h4>Output</h4>\r\n\r\n- Đưa ra một số nguyên – chênh lệch nhiệt độ tối thiể có thể đạt được. Nếu không thể cứu được thiết bị thì đưa ra số `-1`.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4 3\r\n        ..f\r\n        ..#\r\n        s##\r\n        ...\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        0\r\n        ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}