小X挑战跳迷宫

题目来源

原创 / 参考OJ(补个原题链接:link:

题目描述

小X来到了一个迷宫中,它可以上下左右一个方向走一个,也可以隔着一个墙跳过去。
起点是 (1,1) 终点是 (n,n) 问小X最少要几步可以走到终点( n\le1000 )。

输入格式

第一行一个整数 n
接下来 n 行每行 n 个字符。

输出格式

一行一个整数,表示答案。

样例

Input 1

4
.###
...#
####
.#..

Output 1

5