trang chủ / đề bài / icpc20_nat_b

Trận chiến Hogwarts

Đề bài

Mô tả

Kẻ thù đang tiến vào Trường Phù thủy và Pháp sư Hogwarts. Hãy giúp Harry và các bạn bảo vệ ngôi trường!

Hogwarts có thể xem như một lưới gồm r hàng và c cột. Các hàng được đánh số từ 1 đến r từ trên xuống dưới, các cột được đánh số từ 1 đến c từ trái sang phải. Ô ở hàng i, cột j được ký hiệu là (i,j).

Có 3 loại ô:

  • Tường: kẻ thù không thể đi vào các ô này.
  • Bình thường: kẻ thù có thể đi vào các ô này. Harry có thể dùng phép thuật để chặn các ô này.
  • Kháng phép: kẻ thù có thể đi vào các ô này, nhưng Harry không thể chặn chúng.

Kẻ thù tiến vào từ ô (1,1). Chúng có thể di chuyển giữa hai ô kề cạnh nhau. Tuy nhiên, chúng không thể đi vào ô tường hoặc ô bình thường đã bị Harry chặn.

Harry phải ngăn không cho kẻ thù đến được ô (r,c). Để làm điều đó, cậu có thể dùng phép thuật chặn một số ô bình thường. Lưu ý rằng nếu ô (1,1) hoặc ô (r,c) là tường hoặc bị Harry chặn, thì kẻ thù không thể đi từ ô (1,1) đến ô (r,c).

Tuy nhiên, thời gian không còn nhiều! Harry cần biết số ô bình thường ít nhất cần chặn. Hãy giúp cậu ấy!

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu gồm:

  • Dòng đầu tiên chứa hai số nguyên dương r và c (1≤r·c≤106).
  • r dòng tiếp theo, dòng thứ i chứa đúng c ký tự. Mỗi ký tự là một trong các ký tự sau:
    • # là ô tường;
    • . là ô bình thường;
    • @ là ô kháng phép.

Dữ liệu vào kết thúc bằng hai số 0, và bạn không cần xử lý bộ dữ liệu này.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra đúng một dòng chứa số ô bình thường ít nhất Harry cần chặn để kẻ thù không đến được ô (r,c). Nếu không thể làm được, in ra −1.

Ràng buộc

  • 1≤r·c≤106 với mỗi bộ dữ liệu.
  • Tổng r·c qua tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
4 4
@..#
....
....
#..@
4 4
@..#
..#.
.#..
#..@
0 0
2
0
Ở bộ dữ liệu thứ nhất, Harry có thể chặn 2 ô (2,3) và (3,2); không thể chặn 1 ô hoặc ít hơn mà vẫn ngăn được kẻ thù đến ô (4,4). Ở bộ dữ liệu thứ hai, các ô tường (1,4), (2,3), (3,2), (4,1) đã chia cắt hai góc, nên không cần chặn ô nào.
1 1
.
1 1
@
1 1
#
1 3
@.@
2 2
@@
@@
0 0
1
-1
0
1
-1
Ví dụ bổ sung (không có trong đề gốc). Trong ba bộ đầu, ô (1,1) cũng là ô (r,c): ô bình thường thì chặn nó, ô kháng phép thì không thể, ô tường thì không cần chặn gì. Với lưới 1×3, chặn ô giữa. Lưới cuối toàn ô kháng phép nên không thể.

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