Đếm đường viền
Đề bài
Mô tả
Một đảo đệ quy là một hòn đảo nằm trong một hồ nước (hồ này có thể lại nằm trong một hòn đảo khác). Một hồ đệ quy là một hồ nước nằm trong một hòn đảo (đảo này có thể lại nằm trong một hồ khác).
Bash rất thích ý tưởng này. Anh muốn vẽ một số bức tranh gồm các đảo và hồ, trong đó có thể có đảo, hồ đệ quy.
Bash có một lưới gồm hàng và cột, chia thành ô. Bash tô một số ô màu đỏ và một số ô màu xanh lá.
Bây giờ Bash muốn vẽ một số đường viền không giao nhau trên lưới. Một đường viền là ranh giới giữa đất liền và mặt nước, và phải thỏa mãn các điều kiện sau:
- Nó là một đa giác, mọi đỉnh của nó là tâm của các ô không được tô màu.
- Mọi cạnh song song với các trục tọa độ.
- Nó không tự cắt (kể cả không tự chạm vào chính nó tại một điểm).
- Không cạnh nào đi qua ô được tô màu.
Một đường viền có thể nằm hoàn toàn bên trong một đường viền khác. Tuy nhiên, không có điểm nào được nằm trên hai đường viền khác nhau (hai đường viền cũng không được chạm nhau tại một điểm).
Như vậy mỗi đường viền là một đường gấp khúc khép kín đi dọc theo các đoạn thẳng nối tâm của hai ô kề cạnh nhau, chỉ đi qua tâm các ô không tô màu. Các cách vẽ sau là không hợp lệ: có cạnh không song song với trục; có đỉnh không phải tâm ô; đường viền đi qua ô được tô màu; hai đường viền cắt hoặc chạm nhau; một đường viền tự cắt; một đường không khép kín (không phải đa giác).
Sau khi vẽ xong các đường viền, Bash tô đất liền và mặt nước vào các phần giữa các đường viền sao cho:
- Với mỗi đường viền, phần bên trong và phần bên ngoài nó phải khác nhau (một phần là nước, phần kia là đất).
- Các phần chạm vào biên của lưới phải là đất.
Một bức tranh được coi là hợp lệ khi và chỉ khi:
- Mọi ô màu đỏ đều là đất.
- Mọi ô màu xanh lá đều là nước.
Hãy đếm số bức tranh hợp lệ. Hai bức tranh được coi là khác nhau khi và chỉ khi tồn tại một phần nào đó của lưới là đất trong bức tranh này và là nước trong bức tranh kia.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa ba số nguyên , và (; ; ), trong đó là số ô được tô màu.
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên , và một xâu (; ; là red hoặc green), nghĩa là ô được tô màu (red là đỏ, green là xanh lá). Dữ liệu đảm bảo ô này đôi một khác nhau.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa số bức tranh hợp lệ, lấy theo modulo .
Ràng buộc
- .
- , , .
- Tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 3 1 2 2 green 3 3 1 2 2 red |
1 1 |
Bộ thứ nhất: cách duy nhất là một đường viền hình vuông nối tâm của ô ở các góc, bao quanh ô xanh ở giữa thành một hồ. Bộ thứ hai: không thể vẽ đường viền nào vì mọi đường viền trong lưới đều phải đi qua tâm ô giữa hoặc bao quanh nó, nên cả lưới là đất. |
| 3 3 3 0 1 5 1 1 3 green 4 4 2 2 2 green 3 3 green |
14 0 4 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ hai: lưới chỉ có một hàng nên không vẽ được đường viền nào, ô xanh không thể là nước. Bộ thứ ba: hồ phải chứa cả hai ô xanh; có cách tùy việc hồ có mở rộng thêm về phía góc trên phải và góc dưới trái hay không. |
Bình luận