Kỳ thi chọn học sinh giỏi Lớp 12 THPT cấp tỉnh môn Tin học - Sở GD&ĐT Đồng Tháp (Có đáp án)

(Bản scan)

Bài 2. (7.0 điểm) VƯỢT SÔNG -

Nhà của bé Hằng Nga nằm ở bên bờ trái của con sông quê, còn nhà ngoại của bé nằm ở
bên bờ phái của sông. Con đường đọc bờ sông còn có rât nhiều nhánh sông bên trái và bên
phải, có nhánh chây về bên trái, có nhánh chảy vẻ bên phải, có nhánh chảy cả về bên trái và
bên phải.

Yêu cẫu: Bạn có được sơ đồ đoạn sông từ nhà bé Hằng Nga đến nhà ngoại của bé, hãy
chỉ giúp bé Hăng Nga phương án đi đến nhà ngoại sao cho sô lân “wượý sông” là ít nhất.

Dữ liệu vào: Cho từ tệp văn bản VUOTSONG.INP gồm một xâu kí tự độ dài N (N <
10) mô tả bản đồ con sông từ nhà bé Hằng Nga đến nhà ngoại. Kí tự *L` kỉ hiệu có nhánh
sông bên trái, kí tự *R' kí hiệu có nhánh sông bên phải, kí tự “B kí hiệu có nhánh sông cả bên
trái và bền phải.

Dữ liệu ra: Ghi vào tệp văn bản VUOTSONG.OUT một số duy nhất là số lần ít nhất
mà bé Hằng Nga phải vượt sông đề đến nhà ngoại của bé.