Zoo

Μια κρύα νύχτα Χριστουγέννων το 2010, το Ζάγκρεμπ ήταν καλυμμένο από χιόνι. Ο Zdravko αποφάσισε να αφήσει το κάστρο του, να διασχίσει το δρόμο και να κάνει μια βόλτα στο πάρκο Maksimir. Δυστυχώς, την ειδυλλιακή βραδιά του χειμώνα διέκοψε ένα τέρας που κρυβόταν στους διπλανούς θάμνους. Το τέρας πήδηξε μπροστά στον Zdravko, αλλά ο Zdravko βρυχήθηκε έναν δυνατό βρυχηθμό που τρόμαξε το τέρας μακριά. Εν αγνοία του, ένα σωρό ζώα από τον κοντινό ζωολογικό κήπο τρόμαξαν από αυτό το βρυχηθμό. Πιο συγκεκριμένα, μια ομάδα τίγρεων και ταύρων ενοχλήθηκαν τόσο πολύ που αποφάσισαν να δραπετεύσουν από τον ζωολογικό κήπο για να βρουν ένα ωραίο ήσυχο μέρος για ύπνο.

Κατά τη διαφυγή τους, τα ζώα έπρεπε να περάσουν από μια ορθογώνια περιοχή χωρισμένη σε τετράγωνα μονάδων ~R \times C~. Τα ζώα πρέπει να εισέλθουν στην περιοχή από την επάνω αριστερή γωνία και πρέπει να φύγουν από την περιοχή από την κάτω δεξιά γωνία. Για να ξεφύγουν όσο το δυνατόν πιο ήσυχα, τα ζώα θα περάσουν από αυτή την περιοχή ένα-ένα, περπατώντας σε ένα αυθαίρετο μονοπάτι προς τέσσερις γενικές κατευθύνσεις (πάνω, κάτω, αριστερά και δεξιά). Με άλλα λόγια, κάθε ζώο δεν ταξιδεύει απαραίτητα σε ένα συντομότερο μονοπάτι κατά τη διαφυγή του και μπορεί να πατήσει στο ίδιο τετράγωνο μονάδας περισσότερες από μία φορές (συμπεριλαμβανομένης της εισόδου και της εξόδου). Δεδομένου ότι το έδαφος είναι καλυμμένο με χιόνι, τα ζώα αφήνουν ίχνη όταν μπαίνουν μέσα σε μοναδιαία τετράγωνα. Εάν υπάρχει ήδη άλλο αποτύπωμα στο τετράγωνο που πρόκειται να πατηθεί, το ζώο θα σβήσει το προηγούμενο αποτύπωμα και θα αφήσει ένα νέο.

Το καθήκον σας είναι να προσδιορίσετε τον ελάχιστο αριθμό ζώων που έχουν ξεφύγει από τον ζωολογικό κήπο Maksimir με βάση τα ίχνη που έχουν μείνει στην προαναφερθείσα ορθογώνια περιοχή.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~R~ και ~C~ από την περιγραφή της εργασίας.
Οι επόμενες γραμμές ~R~ περιέχουν χαρακτήρες ~C~ που αντιπροσωπεύουν την ορθογώνια περιοχή από την περιγραφή της εργασίας.
Ο χαρακτήρας ~T~ αντιπροσωπεύει το αποτύπωμα μιας τίγρης, ο χαρακτήρας ~B~ αντιπροσωπεύει το αποτύπωμα ενός ταύρου και ο χαρακτήρας ∗ αντιπροσωπεύει το ανέγγιχτο χιόνι.

Μπορείτε να υποθέσετε ότι τα δεδομένα εισόδου είναι τέτοια ώστε τουλάχιστον ένα ζώο εισήλθε στην ορθογώνια περιοχή και ότι κάθε ζώο που εισήλθε στην περιοχή έχει επίσης εγκαταλείψει την περιοχή σύμφωνα με τους κανόνες από την περιγραφή της εργασίας.

Έξοδος

Εξαγωγή του ελάχιστου αριθμού ζώων που έχουν ξεφύγει από τον ζωολογικό κήπο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	45	~2 \le R,\;C \le 100~
2	65	~2 \le R,\;C \le 1000~

Παραδείγματα

input

4 4
TT*T
*TTT
***T
***T

output

1

input

3 5
TTBB*
*T*B*
*TTTT

output

2

Επεξήγηση του 2ου παραδείγματος:

input

7 5
BT***
BTBBB
BTTTB
BBT*B
BBT*B
BBT**
*BBBB

output

3