{"code":"flood","name":"Mùa lũ (OLP 11 - 2019)","description":"Là người yêu thích cuộc sống gắn bó với thiên nhiên, Tâm đã đi thám hiểm nhiều nơi trên thế giới,\r\nvà lập một trang trại nhỏ ở vùng rừng nguyên sinh $Narmia$ để quan sát và chăm sóc các loài động\r\nvật hoang dã có nguy cơ bị tuyệt chủng.\r\n\r\nVùng trang trại của Tâm, đến mùa mưa, nước lũ thường dâng cao, gây ngập lụt nhiều nơi. Mùa mưa\r\nlũ năm nay sắp đến, Tâm cần đến cửa hàng mua thêm lương thực và trang thiết bị cho trang trại của\r\nmình. Do đang bận sửa chữa và dọn dẹp trang trại, Tâm cố gắng trì hoãn việc đi tới cửa hàng lâu\r\nnhất có thể để làm xong công việc tại trang trại.\r\n\r\nChúng ta biết bản đồ của vùng đất mà Tâm đang ở có dạng lưới ô vuông với kích thước $N x M$\r\n(gồm $N$ dòng và $M$ cột). Trang trại của Tâm và cửa hàng tương ứng với hai ô khác nhau trên bản đồ.\r\nỞ một số ô còn có các khe suối. Tại thời điểm $t = 0$, mọi vị trí đều khô ráo. Thời điểm $t = 1$, nước lũ\r\nđồng loạt dâng lên ở các khe suối, các ô có khe suối đều trở nên ngập nước.\r\n\r\nSau đó, cứ mỗi một đơn vị thời gian trôi qua, một ô chưa ngập kề cạnh với ít nhất một ô đã ngập thì\r\ncũng sẽ bị ngập theo. Tâm có $K$ chiếc bè, Tâm có thể dùng những chiếc bè này như sau:\r\n- Tâm có thể đặt mỗi lần một bè tại một ô bất kì. Khi đã đặt bè, Tâm có thể đi qua ô đó bất kể\r\nnó đang ngập hay không. Bè đã đặt không thể thu lại. Thời gian đặt bè là không đáng kể.\r\n- Bè không có tác dụng ngăn cản dòng nước, nước vẫn gây ngập theo quy luật ở trên bất kể có\r\nbè hay không.\r\n\r\nThời gian di chuyển của Tâm là không đáng kể so với thời gian giữa các lần nước dâng; nói cách\r\nkhác, từ lúc Tâm bắt đầu đến lúc Tâm kết thúc hành trình, mực nước sẽ không thay đổi. Từ một ô,\r\nTâm có thể di chuyển sang ô kề cạnh bất kì nếu ô đó chưa bị ngập, hoặc nếu Tâm di chuyển sang\r\nmột ô có bè.\r\n\r\n#### Yêu cầu: \r\n- Bạn cần giúp Tâm tính thời điểm khởi hành muộn nhất từ trang trại mà vẫn tới được cửa\r\nhàng. Giả sử trang trại của Tâm và cửa hàng được xây dựng trên những ô đất đủ cao và không bao\r\ngiờ bị ngập.\r\n\r\n#### Input\r\n- Dòng đầu chứa ba số nguyên $N, M, K$ ($1 ≤ N, M ≤ 1000, 1 ≤ K ≤ 10000$), lần lượt là kích\r\nthước (số dòng và số cột) của vùng đất mà Tâm ở và số bè Tâm có.\r\n- $N$ dòng tiếp theo, mỗi dòng chứa một chuỗi $M$ kí tự, kí tự thứ $j$ của dòng thứ $i+1$ là `.` nếu ô\r\n($i, j$) trống, là `H` nếu là trang trại của Tâm, là `G` nếu là cửa hàng, là `S` nếu là khe suối.\r\n- Đảm bảo mỗi bản đồ chứa đúng một kí tự `H`, đúng một kí tự `G` và ít nhất một kí tự `S`.\r\n\r\n#### Output\r\n- Ghi ra duy nhất một số nguyên là thời điểm khởi hành muộn\r\nnhất của Tâm. Nếu Tâm có thể khởi hành muộn tùy ý, in ra –1.\r\n\r\n\r\n#### Scoring: \r\n - 40% số điểm của bài tương ứng với các test có $N, M ≤ 50$\r\n \r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        5 5 2\r\n        H....\r\n        .....\r\n        .....\r\n        S....\r\n        ....G\r\n    ???+ success \"Output\"\r\n        5\r\n    ??? warning \"Note\"\r\n        - Trang trại của Tâm ở ô (1, 1) và cửa hàng ở ô (5, 5). Tâm có thể đợi nước lũ dâng 5 lần\r\n        rồi bắt đầu di chuyển, đặt bè ở các ô (1, 2) và (4, 5) trong quá trình di chuyển.\r\n\r\n------------\r\n*Nguồn: Olympic 30/4 năm 2019.*","points":300.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}}