#566. CIRCUS - Biểu diễn xiếc

Xe đạp một bánh là hình ảnh quen thuộc trong các tiết mục biểu diễn xiếc. Để tăng tính hấp dẫn cho tiết mục, đạo diễn quyết định "tin học hoá" nó: chia bánh xe đạp đặc (không có nan hoa) thành sector, mỗi sector và sơn trong màu khác nhau đánh số từ đến . Sàn diễn được chia thành lưới ô vuông, mỗi ô vuông có cạnh bằng chu vi của bánh xe. Như vậy khi bánh xe tiếp xúc với sàn tại tâm của ô vuông theo một màu nào đó, thì sang ô bên cạnh - màu khác sẽ tiếp xúc với nó (Màu thành , thành , thành , thành , thành ).

Diễn viên phải xuất phát từ ô ban đầu tiến tới ô đích sau khoảng thời gian ngắn nhất theo các qui tắc sau:

• Quay mặt về phía nào thì phải theo hướng đó;
• Chỉ được phép đi qua các ô trống;
• Tại tâm một ô có thể xoay về phía phải hay trái;
• Xuất phát ở trạng thái màu tiếp xúc với sàn và kết thúc ở với màu tiếp xúc với sàn;
• Mỗi thao tác xoay hoặc chuyển sang ô mới mất giây;
• Ban đầu, diễn viên quay mặt về phía Bắc (Các dòng được đánh số từ đến theo chiều Bắc Nam và các cột được đánh số từ đến theo chiều Tây Đông).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ;
• dòng sau, mỗi dòng chứa một xâu ký tự mô tả trạng thái của các dòng tương ứng với - ô xuất phát, - ô đích, - ô có vật cản, dấu chấm - ô trống.

Dữ liệu ra:

• Thời gian nhanh nhất hoặc , nếu không thể đi được.

Ví dụ:

Dữ liệu vào:

10 10 1 1
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T

Dữ liệu ra:

49