Chó soi và cừu non ^^

Giống như cái đề vậy, bài này liên quan đến sói và cừu.

Ông chủ chăn cừu nọ có một cách đồng để nuôi cừu. Cách đồng gồm nhiều ô nhỏ (mô phỏng mảng hai chiều ^^), mỗi ô này có thể có một con cừu đứng ở đó, một đống gai (để xếp tạo thành hàng rào) hoặc không có gì cả. Một hôm, ông chủ đi vắng, một bầy sói nọ đã đột nhập vào cách đồng bằng một cách không rõ nào đó. Vì cánh đồng có hàng rào chắn nên có thể được chia thành nhiều miền khác nhau. Trong mỗi miền đều có thể bị sói đột nhập.

a) Hãy xác định xem sói đã đột nhập vào mấy miền. (dễ ^^)
b) Trong mỗi miền, nếu số cừu ít hơn hoặc bằng số sói thì toàn bộ cừu sẽ bị ăn thịt sạch, ngược lại, nếu số cưu nhiều hơn thì chúng sẽ không bị ăn thịt. Hãy đếm xem có bao nhiêu con cừu bị ăn thịt.
c) Thực ra "cách không rõ nào đó" đã giúp các con sói đã đột nhập vào cách đòng là do một người xấu đặt vào (giả sử thế đi ). Người xấu này rất ghét ông chủ chăn cừu. Hãy tính xem số lượng cừu tối đa có thể bị giết chết bởi m con sói.

Dữ liệu vào của a và b:

File soivacuu.inp gồm một bản đồ dấu, dấu '.' tương trưng cho ko có gì cả, dấu '*' tượng trưng cho ô có rào gai, kí tự 'c' cho ô có cừu, kí tự 's' cho ô có sói. Lưu ý, mỗi ô trên cánh đồng chỉ được phép chứa một thứ duy nhất là rào gai, sói, cừu hoặc không có gì cả.

Dữ liệu ra đối với a và b là file soivacuu.out. Nếu câu a thì ghi 1 dòng duy nhất là số miền bị sói đột nhập. Nếu là câu b thì ghi 1 dòng duy nhất là một số biểu thị số cừu bị ăn thịt.

Dữ liệu vào của câu c là file batcuu.inp dồm một bản đồ dấu: dấu '.' nếu là ô trống, kí tự 'c' nếu chứa cừu, dấu '*' nếu chứa rào gai.

Dữ liệu ra của câu c là file batcuu.out ghi 1 dòng biểu thị số cừu tối đa có thể bị ăn thịt.

Ví dụ nhé, câu a và b thôi.

Ví dụ với bản đồ 10*15 sau:



Thì bản đồ sẽ có 8 miền.

có 5 miền bị sói đột nhập và trong đó có 9 con cừu bị ăn thịt.

Bạn thường có một thói quen không giới hạn dữ liệu. Theo mình thì thói quen đó là không tốt. Vì một bài toán cái quan trọng nhất là giới hạn dữ liệu. Nó làm ảnh hưởng đến ý tưởng để giải 1 bài toán.

Ví dụ như thế này:
Đối với bài toán sắp xếp các số nguyên:
- Nếu số liệu nhỏ thôi (n< 10000) thì ta sẽ dùng 2 vòng for giải cho nó dễ
- Nếu số liệu lớn hơn một chút (10000< n < 10^7) ta phải dùng đến quick sort
- Nếu số liệu rất lớn ( 10^7 <n < 3*10^8) thì ta phải dùng đến phép thống kê.

Nói tóm lại bạn nên cho giới hạn dữ liệu ở mỗi bài toán.

Đối với bài ở trên nếu dữ liệu nhỏ thôi thì dùng 3 vòng for là đơn giản nhất. Ok

mình và lit mới học lớp 9 nên cũng chưa rõ lắm về giới hạn dữ liệu và cách tính thời gian chạy chương trình. [You must be registered and logged in to see this link.] có thể chỉ cho em dc ko?

Ad có thể chỉ littlelee về phép thống kê được ko. Littlelee chưa bao giờ nghe nói đến thuật toán này cả.