علقت Bessie مجددًا بالجانب الخطأ من حظيرة Farmer John، وبصرها ضعيف فتحتاج مساعدتك لعبورها.
الحظيرة شبكة $N \times N$ من خلايا مربعة ($2 \leq N \leq 20$)، فارغة أو فيها قش لا يُجتاز. تبدأ من أسفل اليسار $(1,1)$ إلى أعلى اليمين $N,N$. الأوامر «تقدم» و«دُر يسارًا 90 درجة» و«يمينًا 90 درجة». أعطِ أقصر تسلسل. إذا حاولت الخروج، نحو الجدار، أو دخول القش، فلا تتحرك وتتجاوز للأمر التالي.
لا تعرف هل تبدأ نحو الأعلى $(1,2)$ أم اليمين $(2,1)$. يجب أن ينجح أقصر تسلسل في الحالتين. بعد الوصول تتجاهل بقية الأوامر.
الإدخال
اقرأ من الإدخال القياسي.
يحوي السطر الأول $N$.
الأسطر $N$ التالية تحوي كل منها $N$ محرفًا بالضبط. أول محرف في الأخير $(1,1)$، وآخر محرف في الأول $(N,N)$.
H للقش وE للخلية الفارغة.
$(1,1)$ و$N,N$ فارغتان، ويُضمن مسار خلايا فارغة من $(1,1)$ إلى $N, N$.
الإخراج
اكتب إلى الإخراج القياسي.
اطبع طول أقصر تسلسل يوصل للهدف سواء بدأت للأعلى أم لليمين، في سطر واحد.
أمثلة
الإدخال 1
3 EHE EEE EEE
الإخراج 1
9
ملاحظة
«تقدم، يمين، تقدم، تقدم، يسار، تقدم، يسار، تقدم، تقدم» ينجح في كلا الاتجاهين بالمثال.
مؤلف المسألة: Brian Dean