Cho một ma trận lưới  n*m, các ô vuông có bốn màu màu trắng, đen, xanh lá cây và đỏ. Từ một ô vuông có thể đi sang 4 ô kề cạnh. Viết chương trình tìm số lượng ô đen ít nhất có thể trên đường đi từ (x,y) đến (u,v) .

• (i,j) là ô hàng   i, cột j .
• Ký tự ∗ là ô màu đen.
• Ký tự . là ô màu trắng.
• Ký tự  G là ô (x,y)  có màu xanh lá cây.
• Ký tự R là ô  (u,v) có màu đỏ.
• Luôn tồn tại đường đi từ (x,y)  đến  (u,v).

Dữ liệu

• Dòng đầu tiên: Hai số nguyên dương n  và m
•  dòng tiếp theo: Mô tả ma trận lưới.
• Giới hạn:   n,m<=1000

Kết quả

• Kết quả của chương trình.