Replication

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một robot tự nhân bản được đặt trên lưới $N \times N$ chứa đá và ô trống. Robot bắt đầu tại các ô được đánh dấu 'S'. Mỗi giờ, robot có thể di chuyển theo 4 hướng (tất cả bản sao cùng di chuyển). Cứ mỗi $D$ giờ, mỗi robot tạo ra bản sao tại 4 ô kề (bản gốc vẫn ở vị trí cũ). Nếu robot hoặc bản sao đi vào ô có đá, tất cả đều tắt.

Đếm số ô trống có thể chứa robot tại một thời điểm nào đó.

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $D$
N dòng tiếp theo: mỗi dòng N ký tự mô tả lưới
- '.' hoặc 'S' = ô trống (S = vị trí bắt đầu)
- '#' = đá
- Tất cả ô biên là đá

Dữ liệu ra

Một số nguyên duy nhất - số ô có thể chứa robot.

Ràng buộc

$3 \leq N \leq 1000$
$1 \leq D \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
10 1 ########## #........# #S.......# #........# ########## #S....S..# ########## ########## ########## ##########	15	Với D=1, robot nhân bản mỗi giờ nên chỉ di chuyển được giới hạn trước khi nhân bản vượt quá vùng trống.

Bình luận

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