Điều hướng bò

Lưới $N\times N$ gồm ô trống (E) và kiện cỏ (H). Bessie ở $(1,1)$ cần đến $(N,N)$. Ban đầu không biết hướng (lên hoặc phải). Chuỗi lệnh phải đưa Bessie đến đích bất kể hướng ban đầu. Lệnh: tiến, quay trái, quay phải. Nếu tiến vào tường/kiện cỏ thì đứng yên.

Tìm độ dài chuỗi lệnh ngắn nhất.

Dữ liệu vào

• Dòng đầu: $N$.
• $N$ dòng tiếp: lưới (H/E). Hàng 1 = hàng trên cùng.

Dữ liệu ra

Độ dài chuỗi lệnh ngắn nhất.

Ràng buộc

• $2\le N\le 20$

Ví dụ