Cho một ma trận lưới mxn, có các ô bị chặn. Từ một ô vuông có thể đi sang 4 ô kề cạnh nhưng không được đi vào ô bị chặn. Viết chương trình tìm độ dài đường đi ngắn nhất từ (x,y)  đến (u,v) .

• (i,j) là ô hàng i,  cột j .
• Ký tự ∗ là ô bị chặn.
• Ký tự . là ô không bị chặn.
• Ký tự G là ô (x,y) - Green
• Ký tự R là ô (u,v)  - Red
• 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
• n 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.