Spritzbombe
Problem
Es gibt ein Feld in der Größe von NxM. In jeder Zelle kann entweder ein Reagenz A oder B liegen oder nichts liegt - 0. Pro Zug kann man das Reagenz A in eine Zelle legen, wobei die Umwandlung der Materie nach der folgenden Regel erfolgt: 0+ A-& gt; A, A+A-& gt; B, B+A->0. Dabei tritt als Ergebnis der letzten Reaktion eine Explosion auf, und die benachbarten nicht leeren Zellen auf den Seiten der Welt (falls vorhanden) werden von einem Teil des Reagens A getroffen. Punkte pro Zug = Anzahl der Explosionen minus 1. Die Punkte für die einzelnen Züge werden addiert. Es ist erforderlich, das Feld zu löschen und gleichzeitig die maximale Anzahl an Punkten zu erzielen.
Eingabe
In der ersten Zeile werden N und M eingegeben (1 <= N, M <= 3). Als nächstes kommen N Zeilen mit M Zeichen aus dem Alphabet (0, A, B) - die Beschreibung des Feldes.
Ausgabe
Geben Sie eine einzige Zahl aus - die maximale Anzahl an Punkten, die Sie erzielen können.
Kommentar zum zweiten Beispiel: Im ersten Zug gab es keine Explosion, Punkte =0-1=-1; im zweiten Zug gab es eine Explosion und das Feld wurde gelöscht, Punkte =1-1=0; Gesamtpunkte: 0+(-1)=-1
|
Eingabe |
Ausgabe |
1 1
0 |
0 |
1 1
A |
-1 |