Bài 1: Gặm cỏ Bessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối. Bessie đã chia đồng cỏ của mình là một hình chữ nhật thành các ô vuông nhỏ với R (1≤R≤100) hàng và C (0≤C≤100) cột, đồng thời đánh dấu chỗ nào là cỏ, chỗ nào là đá. Bessie đứng ở bị trí R_b, C_b và muốn ăn cỏ theo cách của mình, từng ô vuông 1 và trở về chuồng ở ô 1,1; bên cạnh đó đường đi này phải ngắn nhất. Bessie có thể đi từ 1 ô này sang 4 ô vuông kề cạnh. Dưới đây là một bản đồ ví dụ với đá (‘*’) và cỏ (‘.’), chuồng bò (‘B’) và Bessie C ở hàng 5 cột 6 và một bản đồ cho biết hành trình tối ưu của Bessie. Đường đi được đánh dấu bằng chữ ‘m’ | 1 | 2 | 3 | 4 | 5 | 6 | 1 | B | m | m | m | * | . | 2 | . | . | * | m | m | m | 3 | . | * | * | . | * | m | 4 | . | . | * | * | * | m | 5 | . | . | * | * | * | m | 6 | * | . | . | * | . | m | Bessie ăn được 9 ô cỏ Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie ăn được trên con đường ngắn nhất trở về chuồng. (chuồng không có cỏ) Dữ liệu vào: trong file VMUNCH.INP Dòng 1: Hai số nguyên cách nhau bởi dấu cách Dòng 2..R+1: Dòng thứ i+1 mô tả dòng i với C ký tự (không có dấu cách) Dữ liệu ra: trong file VMUNCH.OUT Là một số nguyên duy nhất là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuông Ví dụ: -
VMUNCH.INP | VMUNCH.OUT | 5 6 B…*. ..*… .**.*. ..***. *..*.C | 9 | Bài 2: Tương đương hóa hai từ
Cho hai từ x, y và một dãy hữu hạn các từ (w1, w2, ..., wk).
Phép toán p * q mang ý nghĩa là phép nối từ p với từ q, hay nói cách khác p * q là một từ mới tạo thành bằng cách viết từ q phía sau từ p. Ta cần kiểm tra xem hai từ x, y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước không.
Ví dụ: Từ abba và ab có thể tương đương hóa bằng cách sử dụng các từ trong dãy: baaabad aa badccaa cc. Ta cần nối vào từ abba các từ: aa và badccaa, và nối vào từ ab các từ baaabad, cc và aa theo thứ tự. Trong cả hai trường hợp, ta sẽ thu được cùng một từ: abbaaabadccaa.
Yêu cầu
Cho biết từ x, từ y và dãy từ w1, w2, ..., wk. Cho biết từ x và y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước được hay không? Nếu có thể, hãy tìm số lượng nhỏ nhất phép toán * cần sử dụng.
Dữ liệu -
Dòng đầu tiên chứa một số nguyên dương k ≤ 40.
-
Dòng thứ hai và dòng thứ ba mô tả từ x và y.
-
K dòng tiếp theo mô tả dãy từ w1, w2, ..., wk, mỗi từ trên một dòng.
-
Mô tả của mỗi từ chứa một số nguyên cho biết độ dài của từ, theo sau bởi khoảng trắng và một chuỗi thể hiện từ đó.
-
Mỗi từ chỉ bao gồm các chữ cái Latin in thường và có độ dài không vượt quá 2000.
-
Tổng độ dài các từ không vượt quá 5000.
Kết quả -
Nếu không tồn tại lời giải, in ra 'NIE'.
-
Nếu tồn tại lời giải, in ra một số nguyên dương, là số lượng nhỏ nhất các phép toán * cần để tương đương hóa hai từ x và y.
Ví dụ VWORDS.INP | VWORDS.OUT |
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc
|
5
|
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa
|
NIE
|
Chia sẻ với bạn bè của bạn: |