scor pion

Time limit: 0.1s Memory limit: 64MB Input: scor-pion.in Output: scor-pion.out

Ștefan se joacă un joc folosind o tablă de șah de NN pe MM pătrățele. Tabla este formată din spații libere (.), dar și din spații ocupate de piese adverse: Regine (R, 99 puncte), Turnuri (T, 55 puncte), Cai (C, 33 puncte) și Nebuni (N, 33 puncte). Acesta vrea să afle care este cel mai mare scor pe care îl poate obține un pion pus pe primul rând al acestei table de șah, dacă scorul unui pion este suma punctelor pieselor capturate.

Un pion se poate muta în 22 moduri pe o tablă de șah:

  1. Cu o pătrățică în față, doar dacă pătratul din fața sa este liber;
  2. Cu o pătrățică pe diagonală în față-stânga sau față-dreapta, doar dacă pe pătrățica pe care urmează să se mute se află o piesă adversă. Acea piesă va fi capturată iar punctajul ei va fi adunat la scorul pionului.

Cerință

Dându-se dimensiunea și configurația tablei de șah, aflați care este scorul maxim pe care îl poate obține un pion plasat pe primul rând al acestei table de șah. Se garantează că nicio piesă adversă nu blochează pozițiile de start.

Date de intrare

Pe prima linie a fișierului de intrare scor-pion.in se găsesc două numere întregi, NN și MM, dimensiunile tablei de șah.
Pe fiecare dintre următoarele NN linii se găsește câte un șir de MM caractere, reprezentând câte un rând din tabla de șah. Se garantează că primul rând (cel mai de jos) este complet liber.

Date de ieșire

Pe prima linie a fișierului de ieșire scor-pion.out se va găsi un singur număr întreg, cel mai mare scor pe care îl poate obține un pion plasat pe tabla de șah.

Restricții și precizări

  • 5N,M5005 \leq N, M \leq 500;
  • Tabla este formată doar din caracterele ., R, T, C, N;
  • Se garantează că prima linie a tablei (cea mai de jos) este complet liberă;
# Punctaj Restricții
1 10 Pe tablă se află o singură piesă adversă
2 11 Toate piesele adverse sunt puse pe aceeași linie
3 12 Fiecare rând este fie complet liber, fie plin cu un singur tip de piesă
4 13 Toate piesele adverse sunt puse pe aceeași diagonală, începând fie din colțul din stânga-sus, fie din cel din dreapta-sus, fără spații libere între ele
5 14 Toate piesele adverse sunt puse într-o formă de X, adică două diagonale care se intersectează (cele 44 linii care pornesc din centrul X-ului pot fi de lungimi diferite, dar între piesele de pe ele nu vor fi spații libere)
6 40 Fără restricții suplimentare

Exemplul 1

scor-pion.in

5 5
.....
..R..
....C
.T..N
.....

scor-pion.out

14

Explicație

Acest scor se poate obține plasând pionul pe a 33-a coloană, adică pe pătrățica cu coordonatele {5,3}\{5, 3\}.
După ce capturează turnul de pe poziția {4,2}\{4, 2\} scorul acestuia ajunge la 55 puncte, apoi poate să mute în față ca apoi să captureze regina de la poziția {2,3}\{2, 3\}, ajungând la scorul total de 5+9=145 + 9 = 14 puncte.
Traseul parcurs de pion este: {5,3}\{5, 3\} -> {4,2}\{4, 2\} -> {3,2}\{3, 2\} -> {2,3}\{2, 3\}.

Log in or sign up to be able to send submissions!