תיאור הבעיה

ביטארו חובב האופנה קנה שטיח חדש. לשטיח צורת מלבן המחולק לרשת של $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$.