debaibattle

ấp độ 4
Thành phố chiến đấu
Nhiều người trong chúng ta đã từng chơi trò chơi "Battle city" khi còn nhỏ, và một số người (như tôi) thậm chí còn thường xuyên chơi trò này trên máy tính cho đến tận bây giờ. 







 

Những gì chúng ta đang thảo luận là một phiên bản đơn giản của trò chơi này. Cho một bản đồ chỉ bao gồm các không gian trống, sông, tường thép và tường gạch. Nhiệm vụ của bạn là nhận được phần thưởng càng sớm càng tốt, giả sử rằng không có kẻ thù nào làm phiền bạn (Xem hình ảnh sau). 

 





 

Xe tăng của bạn không thể di chuyển qua sông hoặc tường, nhưng nó có thể phá hủy tường gạch bằng cách bắn. Một bức tường gạch sẽ biến thành không gian trống khi bạn bắn vào nó, tuy nhiên, nếu phát bắn của bạn trúng một bức tường thép, sẽ không có thiệt hại nào cho bức tường. Trong mỗi lượt của mình, bạn có thể chọn di chuyển đến một không gian trống lân cận (4 hướng, không phải 8) hoặc bắn vào một trong bốn hướng mà không di chuyển. Phát bắn sẽ tiến về phía trước theo hướng đó, cho đến khi nó ra khỏi bản đồ hoặc bắn vào một bức tường. Nếu phát bắn trúng một bức tường gạch, bức tường sẽ biến mất (tức là, trong lượt này). Vâng, với mô tả của bản đồ, vị trí xe tăng của bạn và mục tiêu, bạn sẽ mất ít nhất bao nhiêu lượt để đến đó?  

 

Đầu vào

 Có thể có nhiều hơn một trường hợp thử nghiệm trong đầu vào. Dòng đầu tiên có T, số lượng trường hợp thử nghiệm.
Sau đó, tổng số T trường hợp thử nghiệm được cung cấp trong các dòng sau (T <= 10).
Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa hai số nguyên M và N (2 <= M, N <= 300). Mỗi dòng trong số M dòng sau chứa N chữ cái viết hoa, mỗi chữ cái là một trong số 'Y' (bạn), 'T' (mục tiêu), 'S' (tường thép), 'B' (tường gạch), 'R' (sông) và 'E' (khoảng trống). Cả 'Y' và 'T' chỉ xuất hiện một lần. 

Đầu ra

Đối với mỗi trường hợp thử nghiệm, vui lòng xuất ra các lượt bạn thực hiện ít nhất trên một dòng riêng biệt. Nếu bạn không thể đến đích, hãy xuất ra "-1" thay thế.



Vật mẫu

Đầu vào

1

3 4

YBEB

EERE

SSTE

 

Đầu ra

Trường hợp 1

số 8