Lan truyền khối khuẩn ty thể
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