2014-2015 Olympic 10¶
Bài 1: Số vùng dương (5.0 điểm)¶
Đề bài¶
Trên một lưới \(R \times C\), mỗi ô vuông mang một giá trị nguyên.
Yêu cầu: xác định số vùng dương (mang số khác 0). Một vùng dương khi có các cạnh liền kề bất kể hướng.
Dữ liệu vào: trong file văn bản positive.inp với dạng thức:
- Dòng đầu: hai số \(R\) và \(C\) cách nhau ít nhất một khoảng trắng.
- \(R\) dòng kế tiếp: mỗi dòng cho biết \(C\) ký số của dòng.
Kết quả: ghi vào file văn bản positive.out một số duy nhất là số vùng dương tìm được.
Ví dụ:
positive.inp | positive.out |
---|---|
8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0 |
2 |
Giải thích: hai vùng là vùng in đậm và in nghiên.
Bài giải đề xuất¶
Bước 0:
Khởi tạo cấu trúc cell để lưu trữ toạ độ hàng và cột.
Khởi tạo mảng directions
để lưu trữ tám hướng di chuyển khi áp dụng duyệt lưới theo BFS.
Khởi tạo mảng visited
để đánh dấu các ô đã duyệt trong lưới.
Bước 1: Viết hàm để thực hiện duyệt lưới theo BFS.
Bước 2: Duyệt từng ô trong lưới, gọi hàm bfs()
để duyệt lưới và đánh dấu các ô đã duyệt.
Vì hàm bfs()
duyệt và đánh dấu đã duyệt các ô có giá trị dương trong lưới nên khi bfs()
hoàn thành đồng nghĩa đã duyệt xong một vùng dương trong lưới.
Do đó, khi gặp một ô có giá trị dương và chưa duyệt, ta tính đây là ô bắt đầu của một vùng mới, tăng biến đếm region_count
thêm 1.
Mã nguồn¶
Code đầy đủ được đặt tại GitHub.
Bài 2: Vượt sông (7.0 điểm)¶
Đề bài¶
Nhà của bé Cốm 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 dòng bờ sông còn có rất nhiều nhánh sông bên trái và bên phải, cóo 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é Cốm đến nhà ngoại của bé. Hãy chỉ giúp bé phương án đi đến nhà ngoại sao cho số lần "vượt sông" là ít nhất.
Dữ liệu vào: cho từ file văn bản river.inp gồm một xâu ký tự độ dài \(N (N \le 10^6)\) mô tả bản đồ con sông từ nhà bé đến nhà ngoại. Ký tự 'L' ký hiệu nhánh sông bên trái, ký tự 'R' ý 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.
Kết quả: ghi vào file văn bản river.out một số duy nhất là số lần ít nhất mà bé phải vượt sông để đến nhà ngoại của bé.
Ví dụ:
river.inp | river.out |
---|---|
LLBLRRBRL | 5 |
Ràng buộc: có 50% số text tương ứng 50% số điểm của bài có \(N \le 20\).
Bài giải đề xuất¶
Ý tưởng:
Đặt vị trí của xuất phát của Cốm là 0
. Duyệt từng nhánh sông (biểu thị bằng các ký tự trong chuỗi input), mỗi lần duyệt xong một ký tự thì Cốm đến một vị trí mới.
Vì có hai bờ sông nằm ở bên trái và bên phải nên ứng với một vị trí mới của Cốm, ta xét và lưu số lần vượt sông ít nhất tính từ vị trí 0
đến vị trí mới nhất cho cả hai bên bờ sông.
Sau khi duyệt hết chuỗi input, ta so sánh giá trị vượt sông giữa hai bờ thì ra được số lần vượt sông ít nhất tính trên tổng thể để đến được nhà ngoại.
Bước 0:
Gọi River
là chuỗi input. Ta thêm ký tự '0'
vào đầu chuỗi River
nhằm "hợp lý hoá" tiến trình suy luận: để đến được vị trí i
, Cốm phải xét nhánh sông River[i]
.
Khởi tạo hai mảng Left
và Right
. Trong đó:
Left[i]
lưu số lần vượt sông ít nhất để đến được vị tríi
ở bờ trái của sông.Right[i]
lưu số lần vượt sông ít nhất để đến được vị tríi
ở bờ phải của sông.
Do nhà Cốm nằm ở bờ trái và đây là vị trí i == 0
, nên để đến được vị trí 0
của bờ trái, Cốm không cần vượt sông. Còn để đến được vị trí 0
của bờ phải, Cốm phải băng ngang sông, nghĩa là số lần vượt là 1
.
Theo đó, ta khởi tạo Left
và Right
như sau:
Bước 1: Tính số lần vượt sông ít nhất ở cả hai bờ
Duyệt từng nhánh sông bằng biến i
(lưu tại River[i]
) trong phạm vi [1..n - 1]
, cũng chính là duyệt từng vị trí i
mà Cốm đến, lặp thao tác:
-
Xét ba trường hợp
'L'
,'R'
và'B'
của nhánh sôngRiver[i]
. Trong mỗi trường hợp, ta cần xét các cách để Cốm đến được vị tríi
ở bờ trái và vị tríi
ở bờ phải. Các cách đó bao gồm đi từ vị tríi - 1
ở cùng bờ hoặc ở khác bờ. -
Đồng thời, ghi nhận số lần vượt sông ít nhất giữa các cách trên.
Bước 2: Xác định số lần vượt sông ít nhất trên tổng thể
Sau khi đã duyệt xong nhánh sông cuối cùng, cũng là ký tự cuối cùng River[n - 1]
, Cốm có hai cách đi đến nhà ngoại:
- Cách 1: nếu đang đứng ở bờ trái, Cốm cần vượt sông từ bờ trái sang bờ phải, nghĩa là thêm một lần vượt.
- Cách 2: nếu đang đứng ở bờ phải, Cốm không cần vượt sông lần nào nữa.
Mã nguồn¶
Code đầy đủ được đặt tại GitHub.