Dwayne và Megan
Đề bài
Mô tả
Trong một lâu đài được biểu diễn bởi lưới ô có hai người sinh sống là Dwayne và Megan. Lâu đài có các cửa được đánh dấu bằng ký tự '#' và các ô trống được đánh dấu bằng ký tự '.'. Dwayne và Megan chỉ có thể di chuyển theo bốn hướng: lên, xuống, trái, phải.
Một người khác, gọi là Xmen, muốn chia cắt Dwayne và Megan bằng cách khóa tất cả các cửa (không ai đi qua được ô '#') và xây thêm tối đa một cửa mới tại một ô trống bất kỳ trong lâu đài, trừ vị trí hiện tại của Dwayne và của Megan. Xmen thành công nếu sau đó không còn đường đi nào giúp Dwayne và Megan gặp được nhau.
Ví dụ, với lâu đài ở ví dụ thứ nhất, nếu Megan ở ô hàng cột và Dwayne ở ô hàng cột thì Xmen chia cắt được hai người bằng cách xây một cửa ở ô hàng cột nằm giữa họ. Còn nếu Megan ở ô hàng cột và Dwayne ở ô hàng cột (hai ô kề nhau) thì Xmen không thể chia cắt họ.
Hãy đếm số cặp vị trí của Dwayne và Megan để Xmen có thể chia cắt được hai người. Mỗi ô chỉ chứa được một người, nên Dwayne và Megan phải ở hai ô khác nhau. Hai cặp được coi là khác nhau nếu vị trí của Dwayne hoặc vị trí của Megan khác nhau.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và ().
- dòng tiếp theo, mỗi dòng chứa một xâu độ dài gồm các ký tự '#' và '.', trong đó '#' là cửa và '.' là ô trống của lâu đài. Dữ liệu đảm bảo có ít nhất hai ô '.'.
Dữ liệu ra
In ra một số nguyên là số cặp vị trí của Dwayne và Megan mà Xmen có thể chia cắt hai người bằng tối đa một cửa mới.
Ràng buộc
- Lưới có ít nhất hai ô '.'.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 ##.# ##.. .### |
8 | Ô hàng cột tách biệt với ô trống còn lại, cho cặp. Ngoài ra, hai ô hàng cột và hàng cột bị chia cắt khi xây cửa ở ô hàng cột , cho thêm cặp (đổi vai Dwayne và Megan). |
| 2 3 #.. #.# |
2 | Hai ô hàng cột và hàng cột bị chia cắt bởi cửa ở ô hàng cột ; mỗi cách xếp Dwayne và Megan vào hai ô này là một cặp. |
| 2 3 ... ... |
0 | Giữa hai ô bất kỳ luôn có hai đường đi không chung ô trung gian, nên một cửa mới không đủ để chia cắt. |
| 4 5 #...# #.##. ..##. ..##. |
86 | Có ô trống, tạo cặp không phân biệt thứ tự, trong đó cặp chia cắt được, nên đáp án là . |
Bình luận