Nosaukums
Par daudz kārumu (too_fat)
Laika limits
0.20s
Atmiņas limits
64.0 MB
Grūtība
16%

Definīcija

Gudrinieku ciema zinātnieki pēta peļu intelektu. Tie ir izveidojuši dažādus labirintus un tajos novietojuši kārumus. Pēc tam tie labirintā palaiž peli un apskata, cik kārumu peles spēj atrast. Taču ir novērota problēma – daudzas no gudrākajām pelēm ir saēdušās tik daudz kārumu, ka tās ir kļuvušas resnas. Palīdzi zinātniekiem noskaidrot, cik kārumu dotajai pelei labirintā ir iespējams atrast.

Labirits sastāv no N × M kvadrātainām šūnām ur šūna ir vai nu neapstaigājams šķērslis (apzīmējam ar 'X'), apstaigājama šūna bez kāruma (apzīmēta ar '.'), vai apstaigājama šūna ar kārumu (apzīmēta ar '*'). 

Peles labirintā tiek apskatītas kā kvadrāts platumā un augstumā K. Šūnas, kurās pele sākotnēji atrodas, ir apstaigājamas un apzīmētas ar 'P'. Pele pārvietojas pa vienai šūnai vai nu vertikāli, vai horizontāli. Un tā var apēst visu, kam tā uzkāpj virsū.

Izvadiet vienu skaitli – cik kārumu pelei ir sasniedzami dotajā labirintā.

Ilustrācija

Ilustrācija


Ievaddatu raksturojums

Pirmajā rindā doti divi veseli skaitļi N un M (3 < N, M ≤ 2000), labirinta izmērs.

Otrajā rindā dots vesels skaitlis K (0 < K < N, M), peles izmērs.

Tālāk seko N rindas ar M kolonām – labirinta apraksts.


Izvaddatu raksturojums

izvadiet viens veselu skaitli, cik kārumus var apēst pele.


Piezīmes

Apakšgrupas:

  • 20% testu K = 1
  • 20% testu N, M ≤ 500

 


Paraugdati

Stdin
6 10
2
*......X*X
.X...PP.*.
**X..PP...
..X.......
.....XX..X
........*.
Stdout
4

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.