Ba Quốc Gia
Cho bản đồ là một bảng hình chữ nhật gồm hàng và cột. Mỗi ô trên bản đồ được biểu diễn bằng một ký tự với các ý nghĩa sau:
- Các ký tự
1,2,3biểu thị ô thuộc về quốc gia tương ứng (1, 2 hoặc 3). - Ký tự
.biểu thị một ô trống có thể xây đường đi qua. - Ký tự
#biểu thị một ô không thể xây đường (cấm xây).
Một ô được gọi là đi được nếu nó thuộc về một trong ba quốc gia, hoặc đã được xây đường tại đó. Từ một ô đi được, ta có thể di chuyển sang ô đi được liền kề theo bốn hướng lên / xuống / trái / phải, miễn là ô đó tồn tại trong bảng.
Hãy tìm số lượng ô tối thiểu cần xây đường (chỉ được xây trên các ô .) sao cho từ một ô bất kỳ của một quốc gia có thể đi tới một ô bất kỳ của hai quốc gia còn lại thông qua các ô đi được. Nếu không thể đạt được mục tiêu, in ra .
Đảm bảo rằng ban đầu các ô cùng thuộc một quốc gia đã liên thông với nhau (chỉ đi qua các ô của quốc gia đó), và mỗi quốc gia có ít nhất một ô trên bản đồ.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và () — số hàng và số cột.
- dòng tiếp theo, mỗi dòng chứa ký tự mô tả các hàng của bản đồ.
Dữ liệu ra
In ra một số nguyên duy nhất — số ô tối thiểu cần xây đường, hoặc nếu không thể.
Ràng buộc
- Mỗi ký tự trên bản đồ thuộc tập
1,2,3,.,#. - Các ô cùng quốc gia ban đầu đã liên thông; mỗi quốc gia có ít nhất một ô.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 5 11..2 #..22 #.323 .#333 |
2 | Xây đường tại ô . (ví dụ và ở hàng đầu) là đủ để nối ba quốc gia. |
| 1 5 1#2#3 |
-1 | Hai ô # chặn hoàn toàn nên không thể nối ba quốc gia. |
| 3 1 3 1 2 |
0 | Ba quốc gia đã liền kề theo chiều dọc, không cần xây thêm đường. |
Bình luận