Mê cung sinh tồn

Ở một vùng đất chìm trong tĩnh lặng và đá tảng, một chiến binh đơn độc tên Riven tỉnh dậy bên trong một mê cung chết chóc. Anh không nhớ mình đã đến đây bằng cách nào, chỉ biết sứ mệnh của mình: tới được điểm đích trước khi cạn kiệt sức lực.

Mặt đất xung quanh tạo thành một hoa văn kỳ lạ, như một lưới ô được khắc bởi một bàn tay vô hình. Có ô an toàn, có ô bị nguyền rủa. Một dòng chữ khắc trên tường ghi:

• -: Ô an toàn
• +: Bẫy chết người, mỗi lần bước vào sẽ mất $1$ HP (điểm sinh lực)
• S: Điểm xuất phát, nơi Riven đang đứng
• D: Điểm đích, lối thoát tự do

Riven chỉ còn $3$ HP. Mỗi lần bước vào một ô bẫy, anh mất $1$ HP. Nếu HP giảm về $0$, anh sẽ chết. Mỗi bước di chuyển (lên, xuống, trái hoặc phải sang ô kề cạnh) tốn $1$ đơn vị thời gian.

Yêu cầu: Tìm thời gian ngắn nhất để Riven tới được điểm đích mà vẫn còn sống.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $R$, $C$: số hàng và số cột.
• $R$ dòng tiếp theo, mỗi dòng chứa $C$ ký tự (không có dấu cách) mô tả mê cung. Lưới chỉ gồm các ký tự S (xuất phát), D (đích), + (bẫy) và - (ô an toàn).

Dữ liệu ra

In ra số bước ít nhất để Riven tới điểm đích với HP $>0$. Nếu không có cách nào, in ra $-1$.

Ràng buộc

• $2\le R,C\le 100$
• Lưới có đúng một ô S và đúng một ô D.

Ví dụ