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



tải về 25.4 Kb.
Chuyển đổi dữ liệu30.08.2016
Kích25.4 Kb.
#28226

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ừ abbaab 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ừ: aabadccaa, và nối vào từ ab các từ baaabad, ccaa 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

Каталог: userfiles -> file
file -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
file -> 29 Thủ tục công nhận tuyến du lịch cộng đồng
file -> BÀi phát biểu củA ĐẠi diện sinh viên nhà trưỜng sv nguyễn Thị Trang Lớp K56ktb
file -> CỦa bộ trưỞng bộ VĂn hóa thông tin về việc thành lập tạp chí di sản văn hóa thuộc cục bảo tồn bảo tàng bộ trưỞng bộ VĂn hóa thông tin
file -> BỘ VĂn hoá, thể thao và du lịCH
file -> UỶ ban quốc phòng và an ninh cộng hoà XÃ HỘi chủ nghĩa việt nam
file -> Số: 38/2009/QĐ-ttg CỘng hòa xã HỘi chủ nghĩa việt nam
file -> BỘ VĂn hoá, thể thao và du lịch cộng hoà XÃ HỘi chủ nghĩa việt nam
file -> KỲ HỌp thứ TÁM, quốc hội khóa XIII (20/10/2014 – 28/11/2014)
file -> UỶ ban thưỜng vụ quốc hội ban dân nguyện kỳ HỌp thứ SÁU quốc hội khoá XII

tải về 25.4 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương