Lan truyền khối khuẩn ty thể


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Trong khi chơi Minecraft, Hiệp nhận ra các khối khuẩn ty thể (Mycelium) có khả năng lan truyền. Nếu một ô là khối khuẩn ty thể, các ô là khối cỏ giáp cạnh nó sẽ trở thành khuẩn ty thể sau 1 phút. Ô là khối đá cuội sẽ không trở thành khuẩn ty thể.

Cậu giả sử cậu có một mảnh đất chữ nhật kích thước $M\times N$. Ô $(i,j)$ là khối cỏ khi $c_{i,j}=G$, là khối khuẩn ty thể khi $c_{i,j}=M$, là khối đá cuội khi $c_{i,j}=C$.

Hãy cho biết sau bao nhiêu phút, mảnh đất của Hiệp được phủ bởi khuẩn ty thể (trừ các ô đá cuội).

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $M,N \ (1\le M,N \le 10^3)$;
  • $M$ dòng tiếp theo, mỗi dòng chứa $N$ kí tự $c_{i,j} \ (c_{i,j} \in { G, C, M } )$.

Dữ liệu đảm bảo luôn có khối khuẩn ty thể trong mảnh đất.

Kết quả

  • Kết quả bài toán.

Ví dụ

Ví dụ 1

input

5 6
GGGGGM
GMGGGC
GGMCGG
GGGCGG
MGGCGG

output

6

Comments

There are no comments at the moment.