trang chủ / đề bài / icpc23_mt_d

Bom

Đề bài

Mô tả

Alice đang chơi một trò chơi khác tên là BOOM. Trò chơi có một bản đồ hình chữ nhật kích thước N×M. Mỗi ô 1×1 là một bức tường, một kẻ địch hoặc một ô trống. Trong trò chơi này, một quả bom có tầm nổ theo phương ngang với bán kính V. Nói cách khác, nếu bom được đặt ở ô (i,j) thì tầm nổ của nó là từ ô (i,j−V) đến ô (i,j+V). Không được đặt bom ở ô tường, được phép đặt bom ở các ô còn lại. Bom nổ tại ô được đặt và lan sang hai bên theo phương ngang cho đến khi hết tầm nổ hoặc gặp tường. Lưu ý tường không bị bom phá hủy.

Trong trò chơi này, Alice sẽ mang theo đúng K quả bom. Vì vậy, trước khi vào bản đồ, Alice phải mua K quả bom có cùng tầm nổ V. Để tiết kiệm tiền trong trò chơi, Alice sẽ mua đúng K quả bom với V nhỏ nhất mà vẫn tiêu diệt được tất cả kẻ địch trên bản đồ (Alice không nhất thiết phải dùng hết K quả bom).

Hãy giúp Alice tính V nhỏ nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên dương N,M,K (N×M≤105, K≤105).
  • N dòng tiếp theo, mỗi dòng chứa M ký tự thuộc các loại sau: # là tường, . là ô trống, x là kẻ địch.

Dữ liệu ra

In ra V nhỏ nhất để Alice có thể đặt K quả bom tiêu diệt tất cả kẻ địch. Nếu không có đáp án, in ra −1.

Ràng buộc

  • N×M≤105
  • 1≤K≤105

Ví dụ

Input Output Giải thích
4 6 5
#x..#.
#.x.x#
..#.xx
x....x
1 Với V=1, Alice có thể đặt 5 quả bom ở các ô (1,2), (2,4), (3,5), (4,1), (4,6). Đây là V nhỏ nhất.
2 3 10
xxx
xxx
0 Alice có thể đặt bom ở tất cả các ô của bản đồ.
2 2 1
x.
x.
-1 Alice không thể tiêu diệt tất cả kẻ địch chỉ với 1 quả bom.

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