trang chủ / đề bài / icpc23_mt_i

Dwayne và Megan

Đề bài

Mô tả

Trong một lâu đài được biểu diễn bởi lưới N×M ô 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 1 cột 3 và Dwayne ở ô hàng 2 cột 4 thì Xmen chia cắt được hai người bằng cách xây một cửa ở ô hàng 2 cột 3 nằm giữa họ. Còn nếu Megan ở ô hàng 1 cột 3 và Dwayne ở ô hàng 2 cột 3 (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 N và M (1≤N,M≤500).
  • N dòng tiếp theo, mỗi dòng chứa một xâu độ dài M 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

  • 1≤N,M≤500
  • Lưới có ít nhất hai ô '.'.

Ví dụ

Input Output Giải thích
3 4
##.#
##..
.###
8 Ô hàng 3 cột 1 tách biệt với 3 ô trống còn lại, cho 3·2=6 cặp. Ngoài ra, hai ô hàng 1 cột 3 và hàng 2 cột 4 bị chia cắt khi xây cửa ở ô hàng 2 cột 3, cho thêm 2 cặp (đổi vai Dwayne và Megan).
2 3
#..
#.#
2 Hai ô hàng 1 cột 3 và hàng 2 cột 2 bị chia cắt bởi cửa ở ô hàng 1 cột 2; 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ó 11 ô trống, tạo 55 cặp không phân biệt thứ tự, trong đó 43 cặp chia cắt được, nên đáp án là 2·43=86.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0