Sau khi xem quá nhiều video kỹ thuật "tự làm" trên mạng, Farmer John đã vô tình thả một rô-bốt có khả năng tự nhân bản vào trang trại!

Trang trại được biểu diễn bằng một lưới \(N\times N\) (\(3\le N\le 1000\)), trong đó mỗi ô hoặc trống hoặc chứa đá, và mọi ô trên biên đều chứa đá. Một số ô không có đá được đánh dấu là vị trí có thể đặt rô-bốt ban đầu.

Farmer John đặt rô-bốt ban đầu tại một trong các vị trí có thể xuất phát. Trong mỗi giờ tiếp theo, mọi bản sao của rô-bốt di chuyển phối hợp theo cùng một hướng: bắc, nam, đông hoặc tây.

Sau mỗi \(D\) giờ (\(1\le D\le 10^9\)), mọi bản sao đều nhân bản. Khi một rô-bốt tại ô \((x,y)\) nhân bản, nó tạo các bản sao mới tại \((x+1,y)\), \((x-1,y)\), \((x,y+1)\) và \((x,y-1)\); rô-bốt ban đầu vẫn ở \((x,y)\). Theo thời gian, nhiều rô-bốt có thể cùng chiếm một ô.

Nếu một lần di chuyển hoặc nhân bản khiến bất kỳ rô-bốt nào đi vào ô đá, tất cả rô-bốt lập tức ngừng hoạt động. Do biên trang trại toàn là đá, cuối cùng các rô-bốt chắc chắn phải ngừng.

Hãy giúp đàn bò tìm số ô trống có thể chứa một rô-bốt tại một thời điểm nào đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\), cách nhau bởi dấu cách. Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) ký tự. Mỗi ký tự là ., S hoặc #; . và S đều biểu thị ô trống, trong đó S đánh dấu một vị trí có thể xuất phát, còn # biểu thị đá.

Mọi ký tự ở hàng đầu, hàng cuối, cột đầu và cột cuối đều là #.

Dữ liệu ra

In số ô có thể chứa một rô-bốt tại một thời điểm nào đó.

Phân nhóm

• Các test 4-5 thỏa mãn \(D=10^9\).
• Các test 6-8 thỏa mãn \(D=1\).
• Các test 9-12 thỏa mãn \(N\le 100\).
• Các test 13-20 không có ràng buộc bổ sung.

Ví dụ

10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########

15

##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########

##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########

10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########

28

##########
#x#.xxx..#
#x#xxxxx.#
#xxxxxxxx#
#x#xxxxx.#
#x#.xxx..#
##########
##########
##########
##########

10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########

10

##########
#xx#.....#
#xx#.....#
#xxx.....#
#xx#.....#
#x.#.....#
##########
##########
##########
##########

Nguồn

USACO 2020 December Contest, Gold - Replication: https://usaco.org/index.php?page=viewproblem2&cpid=1065

Tác giả: Benjamin Qi.