COCI 2019/2020 - Contest 1 - Zoo

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 1
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vào một đêm Giáng sinh lạnh giá năm 2010, Zagreb bị bao phủ bởi tuyết. Zdravko quyết định rời lâu đài của mình, băng qua đường và đi dạo qua Công viên Maksimir. Thật không may, đêm đông bình dị đã bị gián đoạn bởi một con quái vật đang ẩn nấp trong bụi cây gần đó. Con quái vật nhảy đến trước mặt Zdravko, nhưng cậu đã nhanh chóng gầm lên một tiếng cực mạnh khiến con quái vật sợ hãi bỏ chạy. Cậu không hề hay biết, một đám động vật từ vườn bách thú gần đó đã giật mình vì tiếng gầm đó. Cụ thể là, một bầy hổ và bò tót đã quá bức xúc nên chúng quyết định trốn khỏi vườn thú để tìm một nơi yên tĩnh đẹp đẽ để ngủ.

Trong quá trình trốn thoát, các con vật phải đi qua một khu vực hình chữ nhật được chia thành ~R \times C~ ô vuông. Những con vật này phải đi vào khu vực qua góc trên bên trái và phải rời khỏi khu vực qua góc dưới bên phải. Để thoát ra ngoài một cách nhẹ nhàng nhất có thể, các con vật sẽ lần lượt đi qua khu vực này, đi dọc theo một con đường tùy ý theo bốn hướng chung (lên, xuống, trái và phải). Nói cách khác, mỗi con vật không nhất thiết phải đi theo con đường ngắn nhất và nó có thể dẫm lên cùng một ô vuông nhiều hơn một lần (bao gồm cả lối vào và lối ra). Vì mặt đất được bao phủ bởi tuyết, các con vật sẽ để lại dấu chân khi chúng bước vào bên trong các ô vuông này. Nếu đã có dấu chân khác trong ô vuông sắp bị dẫm lên, con vật hiện tại sẽ xóa dấu chân trước đó và để lại dấu chân mới.

Nhiệm vụ của bạn là xác định số lượng động vật tối thiểu đã thoát khỏi sở thú Maksimir dựa trên dấu chân đã để lại trong khu vực hình chữ nhật nói trên.

Input

Dòng đầu tiên chứa hai số nguyên ~R~ và ~C~ mô tả số hàng và số cột của khu vực.

~R~ dòng tiếp theo chứa ~C~ ký tự đại diện cho khu vực hình chữ nhật từ mô tả dấu chân của các con vật trên tuyết.

Ký tự T đại diện cho dấu chân của hổ, ký tự B đại diện cho dấu chân của bò và ký tự * đại diện cho ô vuông không có dấu chân.

Dữ liệu đầu vào đảm bảo có ít nhất một con vật đã vào khu vực hình chữ nhật và tất cả các con vật đã vào khu vực đều đã rời khỏi khu vực theo các quy tắc nêu trên.

Output

Đưa ra số nguyên duy nhất là số lượng động vật tối thiểu đã thoát khỏi vườn thú.

Subtask

  • ~15~ test của bài có ~2 \leq R, C \leq 100~
  • ~15~ test của bài có ~2 \leq R, C \leq 1000~

Examples

Sample Input 1
4 4
TT*T
*TTT
***T
***T
Sample Output 1
1
Sample Input 2
3 5
TTBB*
*T*B*
*TTTT
Sample Output 2
2
Sample Input 3
7 5
BT***
BTBBB
BTTTB
BBT*B
BBT*B
BBT**
*BBBB
Sample Output 3
3

Note

Giải thích ví dụ 2:


Comments

Please read the guidelines before commenting.


There are no comments at the moment.