وصف المسألة

اشترى بيتارو المحب للموضة سجادة جديدة. السجادة مستطيلة الشكل مقسمة إلى شبكة من $H$ من الصفوف عمودياً و$W$ من الأعمدة أفقياً، وكل خلية ملونة إما باللون الأبيض أو الأسود. لون الخلية الواقعة في الصف رقم $i$ من الأعلى والعمود رقم $j$ من اليسار ($1 \le i \le H$، $1 \le j \le W$) من السجادة يكون أبيض عندما يكون المحرف رقم $j$ من السلسلة النصية $S_i$ هو .، ويكون أسود عندما يكون #.

ابتكر بيتارو لعبة يضع فيها قطعة في الخلية الواقعة في أقصى أعلى يسار السجادة، ويجعل القطعة تصل إلى الخلية الواقعة في أقصى أسفل يمين السجادة عن طريق إجراء العملية التالية عدة مرات:

• اختر خلية $1$ يختلف لونها عن لون الخلية الموضوعة فيها القطعة حالياً وتجاورها من الأعلى أو الأسفل أو اليسار أو اليمين، وانقل القطعة إلى تلك الخلية.

يريد بيتارو تقليل عدد العمليات اللازمة للوصول إلى أقل حد ممكن. ومع ذلك، اعتماداً على نقش السجادة، قد يكون من المستحيل إيصال القطعة إلى هناك.

بإعطائك معلومات عن نقش السجادة، اكتب برنامجاً لتحديد ما إذا كان من الممكن إيصال القطعة من الخلية العلوية اليسرى إلى الخلية السفلية اليمنى بتكرار العملية، وإذا كان ذلك ممكناً، أوجد أصغر عدد من العمليات.

القيود

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ سلسلة نصية طولها $W$ ($1 \le i \le H$).
• كل محرف في $S_i$ هو . أو # ($1 \le i \le H$).
• $H, W$ عددان صحيحان.

المهام الفرعية

1. ($4$ نقاط) $H = 1$.
2. ($14$ نقطة) $H \le 5$، $W \le 5$.
3. ($24$ نقطة) $H \le 30$، $W \le 30$.
4. ($58$ نقطة) لا توجد قيود إضافية.

الإدخال

يُعطى الإدخال من الدخل القياسي بالصيغة التالية:

H W
S_1
S_2
:
S_H

الإخراج

إذا كان من الممكن إيصال القطعة من الخلية العلوية اليسرى إلى الخلية السفلية اليمنى بتكرار العملية، فاطبع أصغر عدد من العمليات؛ وإذا كان ذلك مستحيلاً، فاطبع -1 في سطر $1$ إلى الخرج القياسي.

أمثلة الإدخال والإخراج

مثال الإدخال 1

4 5
...#.
#####
...#.
#.###

مثال الإخراج 1

9

على سبيل المثال، يمكن التفكير في العمليات الموضحة في الشكل.

في المثال الأيسر يمكن إيصال القطعة من الخلية العلوية اليسرى إلى الخلية السفلية اليمنى في $9$ عمليات، وفي المثال الأيمن في $13$ عملية.

وبما أنه من المستحيل الوصول في أقل من $9$ عمليات، نطبع $9$.

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 4$.

مثال الإدخال 2

3 3
...
...
...

مثال الإخراج 2

-1

توجد حالات لا يمكن فيها إجراء أي عملية منذ البداية. في هذه الحالة، بما أنه من المستحيل إيصال القطعة إلى الخلية السفلية اليمنى، نطبع -1.

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 4$.

مثال الإدخال 3

1 5
.#.#.

مثال الإخراج 3

4

مثال الإدخال هذا يحقق قيود جميع المهام الفرعية.

مثال الإدخال 4

5 5
###.#
.#...
.#..#
.####
##..#

مثال الإخراج 4

12

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 4$.

مثال الإدخال 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

مثال الإخراج 5

12

مثال الإدخال هذا يحقق قيود المهام الفرعية $3, 4$.