Gõ phím
Đề bài
Mô tả
Cần bao nhiêu lần bấm phím để gõ một tin nhắn văn bản? Bạn có thể nghĩ rằng số lần bấm bằng số ký tự của văn bản, nhưng điều này chỉ đúng khi mỗi lần bấm tạo ra một ký tự. Với các thiết bị bỏ túi, khả năng nhập văn bản thường bị hạn chế. Một số thiết bị chỉ có vài nút bấm, ít hơn nhiều so với số chữ cái trong bảng chữ cái. Trên những thiết bị như vậy, có thể cần nhiều lần bấm để gõ một ký tự. Một cách giải quyết hạn chế này là dùng bàn phím ảo hiển thị trên màn hình, với một con trỏ có thể di chuyển từ phím này sang phím khác để chọn ký tự. Bốn nút mũi tên điều khiển việc di chuyển con trỏ, và khi con trỏ nằm trên phím mong muốn, bấm nút thứ năm sẽ chọn ký tự tương ứng và nối nó vào cuối văn bản. Để kết thúc văn bản, người dùng phải di chuyển tới phím Enter và chọn nó. Cách này cho người dùng một bộ ký tự tùy ý và cho phép gõ văn bản dài bao nhiêu cũng được chỉ với năm nút bấm phần cứng.
Trong bài này, bạn được cho bố cục của một bàn phím ảo và cần xác định số lần bấm ít nhất để gõ một văn bản cho trước, trong đó mỗi lần bấm một trong năm nút phần cứng được tính là một lần bấm. Các phím được sắp xếp trên một lưới hình chữ nhật, mỗi phím ảo chiếm một hoặc nhiều ô vuông đơn vị liên thông của lưới. Con trỏ bắt đầu ở góc trên bên trái của bàn phím và di chuyển theo bốn hướng chính, theo cách: con trỏ luôn nhảy tới ô vuông đơn vị gần nhất theo hướng đó thuộc về một phím khác với phím hiện tại. Nếu không có ô vuông nào như vậy, con trỏ không di chuyển.

Hình trên minh họa ví dụ 1: một bàn phím ảo và các nút phần cứng, cùng một cách gõ CONTEST với lần bấm. Các chấm đỏ là những phím ảo mà tại đó nút chọn được bấm.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , lần lượt là số hàng và số cột của lưới bàn phím ảo.
dòng tiếp theo mô tả bàn phím ảo, mỗi dòng gồm ký tự. Mỗi ký tự là một chữ cái in hoa, một chữ số, dấu gạch ngang (-) hoặc dấu sao (*, biểu diễn phím Enter). Mỗi ký tự ứng với đúng một phím. Mỗi phím gồm một hoặc nhiều ô vuông của lưới, luôn tạo thành một vùng liên thông.
Dòng cuối cùng chứa văn bản cần gõ. Văn bản là một xâu khác rỗng gồm các ký tự có trên bàn phím, không chứa dấu sao.
Dữ liệu ra
In ra số lần bấm ít nhất cần thiết để gõ toàn bộ văn bản, tính cả lần chọn phím Enter ở cuối. Dữ liệu đảm bảo văn bản luôn gõ được.
Ràng buộc
- .
- Văn bản có độ dài không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 7 ABCDEFG HIJKLMN OPQRSTU VWXYZ** CONTEST |
30 | Cách gõ trong hình: phải, phải, chọn C; xuống, xuống, trái, trái, chọn O; lên, phải 6 lần, chọn N; xuống, trái, chọn T; lên, lên, trái, chọn E; xuống, xuống, chọn S; phải, chọn T; xuống (tới phím Enter rộng 2 ô), chọn Enter. Tổng cộng lần di chuyển và lần chọn. |
| 5 20 12233445566778899000 QQWWEERRTTYYUUIIOOPP -AASSDDFFGGHHJJKKLL* --ZZXXCCVVBBNNMM--** -------------------- ACM-ICPC-WORLD-FINALS-2015 |
160 | Bố cục giống bàn phím máy tính, phần lớn các phím rộng 2 ô; mỗi lần bấm mũi tên trái hoặc phải nhảy qua cả phím. |
| 2 19 ABCDEFGHIJKLMNOPQZY X*****************Y AZAZ |
19 | Phím Enter dài là đường tắt: chọn A; xuống (X), phải (Enter), phải (nhảy qua cả phím Enter tới Y), trái (về ô cuối của Enter), lên (Z), chọn Z; xuống (Enter), trái (nhảy về X), lên (A), chọn A; lặp lại để gõ Z; xuống, chọn Enter. Tổng cộng lần di chuyển và lần chọn. |
| 6 4 AXYB BBBB KLMB OPQB DEFB GHI* AB |
7 | Chọn A; phải 3 lần tới B ở góc trên bên phải, chọn B; xuống (nhảy qua cả cột của phím B tới phím Enter), chọn Enter. |
Bình luận