trang chủ / đề bài / icpcwf15_f

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 30 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 r và c, lần lượt là số hàng và số cột của lưới bàn phím ảo.

r dòng tiếp theo mô tả bàn phím ảo, mỗi dòng gồm c 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

  • 1≤r,c≤50.
  • Văn bản có độ dài không quá 10000.

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 22 lần di chuyển và 8 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 14 lần di chuyển và 5 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0