Replikasiya
Fermer Con çoxlu video izləməkdən sonra təsadüfən öz-özünü çoxaldan bir robotu fermasında buraxdı!
Ferma n × n ölçüsündə bir şəbəkə kimi təsvir edilir. Burada hər bir hüceyrə ya boşdur, ya da daşla doludur və bütün sərhəd kvadratları daşla doludur. Bəzi daş olmayan hüceyrələr robot üçün mümkün başlanğıc yerləri kimi qeyd olunub.
Fermer Con əvvəlcə robotu mümkün başlanğıc mövqelərindən birinə yerləşdirir. Hər növbəti saatda bütün robot nüsxələri bir istiqamətdə koordinasiyalı şəkildə hərəkət edir: şimal, cənub, şərq və ya qərb. Hər d saatdan bir, hər bir robot nüsxələnir - (x, y) hüceyrəsindəki robot yeni nüsxələr yaradır (x + 1, y), (x − 1, y), (x, y + 1) və (x, y − 1) hüceyrələrində; orijinal robot isə (x, y) hüceyrəsində qalır. Zamanla bir neçə robot eyni hüceyrəni tuta bilər.
Əgər hərəkət və ya nüsxələmə robotlardan birini daşa doğru hərəkət etməyə məcbur edərsə, bütün robotlar dərhal söndürüləcək. Qeyd edək ki, robotlar nəticədə fermanın sərhədinin daşlı olması səbəbindən söndürülməlidir.
İnəklərə hansısa bir anda robotun ola biləcəyi boş kvadratların sayını hesablamağa kömək edin.
Giriş Məlumatları
Birinci sətir iki tam ədəd n (3 ≤ n ≤ 1000) və d (1 ≤ d ≤ 10^9) ehtiva edir. Növbəti n sətirin hər biri n simvol ehtiva edir. Hər bir simvol '.', 'S' və ya '#' simvollarından biri ola bilər. '.' və 'S' boş hüceyrələri, 'S' isə robot üçün mümkün başlanğıc mövqeni göstərir. '#' daş deməkdir.
Birinci və sonuncu sətirdəki, eləcə də birinci və sonuncu sütundakı bütün simvollar '#'-yə bərabərdir.
Çıxış Məlumatları
Bir tam ədəd çıxarın - hansısa bir anda robotun ola biləcəyi hüceyrələrin sayı.
Nümunə
Aşağıdakı diaqramlarda x robotları göstərir. Robotların ola biləcəyi yerlər:
########## #xxx.....# #xxxx....# #xxx.....# ########## #xx..xxx.# ########## ########## ########## ##########
Hadisələrin mümkün ardıcıllığını nəzərdən keçirək:
Con robotu ən sol başlanğıc mövqeyinə qoyur.
Robot bir vahid sağa hərəkət edir.
Robot nüsxələnir.
Bütün robotlar bir vahid sağa hərəkət edir.
İkinci nüsxələmə robot nüsxəsinin daşa doğru hərəkət etməsinə səbəb olacaq, buna görə proses başa çatır.
########## ########## ########## ########## #........# #........# #.x......# #..x.....# #x.......# #.x......# #xxx.....# #.xxx....# #........# #........# #.x......# #..x.....# ########## -> ########## -> ########## -> ########## #........# #........# #........# #........# ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ##########