{"code":"dhbbspell","name":"Ghép chữ (DHBB 2021)","description":"Các bé trường mầm non SuperKids đang chơi trò chơi ghép chữ trên một sân hình chữ nhật kích\r\nthước $m × n$ được chia thành lưới ô vuông đơn vị. Các hàng ô đánh số từ $1$ tới $m$ từ trên xuống\r\nvà các cột ô được đánh số từ $1$ tới n từ trái qua phải. Ô nằm trên giao của hàng $i$ và cột $j$ được\r\ngọi là ô $(i,j)$ và trên đó chứa đúng một chữ cái hoa $a_{ij}$.\r\nMỗi bé khi chơi được cho trước xâu ký tự $S$ độ dài $k$ chỉ gồm các chữ cái hoa. Bé được chọn một\r\nô để xuất phát và thực hiện trò chơi qua nhiều lượt. Tại mỗi lượt, bé bắt buộc phải di chuyển\r\nsang một trong bốn ô kề cạnh với ô đang đứng, sau đó bé được viết ra đúng một chữ cái bằng\r\nvới chữ cái tại ô vừa tới nếu muốn. Mục đích của bé là viết ra được xâu ký tự $S$ đã cho. Chú ý\r\nrằng các chữ cái phải được viết ra lần lượt theo đúng thứ tự trong xâu $S$ và khi tới một ô chỉ\r\nđược viết ra đúng một chữ cái.\r\nYêu cầu: Hãy giúp bé thực hiện được mục đích của mình trong trò chơi với số lần di chuyển ít\r\nnhất. Cho biết số lần di chuyển theo phương án tìm được\r\n\r\n

Input

\r\n\r\nVào từ file văn bản SPELL.INP\r\n- Dòng 1 chứa ba số nguyên dương $m, n, k (2 \\le m, n, k \\le 300)$ cách nhau bởi dấu cách\r\n- Dòng 2 chứa xâu ký tự $S$ gồm đúng $k$ chữ cái hoa viết liền.\r\n- $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ chữ cái hoa liền nhau, chữ cái thứ $j$ là $a_{ij}$\r\n\r\n

Output

\r\n\r\n- Ghi ra file văn bản SPELL.OUT một số nguyên duy nhất là số lần di chuyển ít nhất mà\r\nbé cần thực hiện để đạt được mục đích của trò chơi.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($30\\%$ số điểm): $m, n, k \\le 4$\r\n- Subtask $2$ ($30\\%$ số điểm): $m, n, k \\le 100$\r\n- Subtask $3$ ($40\\%$ số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 2 4 6\r\n DHDBBB\r\n DHAB\r\n ABBD\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 7\r\n ```\r\n \r\n ??? warning \"Note\"","points":1500.0,"partial":true,"time_limit":3.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}}