Nữ hoàng Sofia ở bàn cờ \(n\times m\) có ô bắt đầu S, ô thoát E, ô trống ., và ô chặn #. Một chữ số từ 1 đến 9 nếu xuất hiện sẽ xuất hiện đúng hai lần; khi đáp xuống ô số, Sofia có thể dịch chuyển tức thời sang ô cùng số mà không tốn thêm bước. Sau dịch chuyển tức thời, cô không thể tiếp tục đi cùng hướng mà không trả thêm một bước.

Trong một bước, Sofia có thể nhảy tới bất kỳ ô nào cùng hàng, cột hoặc đường chéo, miễn không có ô chặn giữa hai ô (kể cả hai đầu mút). Hãy tìm số bước ít nhất từ S đến E, hoặc -1 nếu không thể.

Dữ liệu vào

Dòng đầu chứa \(n,m\) (\(1\le n,m\le1000\)). \(n\) dòng tiếp theo chứa bảng gồm các ký tự S, E, ., # và các chữ số 1--9.

Dữ liệu ra

In số bước ít nhất, hoặc -1 nếu không thể đến ô thoát.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(24\) điểm: \(n,m\le5\).
2. \(32\) điểm: không có cổng dịch chuyển.
3. \(18\) điểm: \(n,m\le500\).
4. \(36\) điểm: không có ràng buộc thêm.

Ví dụ

4 4
S..1
####
1.#E
....

4

3 3
S..
.#.
..E

2

5 4
S.21
####
2##1
###.
E..#

4

Nguồn

COCI 2025/2026 - Vòng 1, bài Kraljica.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.