探险家小曹来到了一个N*N的迷宫，起点是左上角(1,1)，终点是右下角(N,N)。迷宫由通道，障碍物和墙壁组成，每一步可以花费单位时间向邻接的上下左右四格的通道移动， 也可以从通道移动到障碍物，清除障碍物需要一定的时间。请求出从起点到终点所需的最少时间。
探险家小曹来到了一个N*N的迷宫，起点是左上角(1,1)，终点是右下角(N,N)。迷宫由通道，障碍物和墙壁组成，每一步可以花费单位时间向邻接的上下左右四格的通道移动， 也可以从通道移动到障碍物，清除障碍物需要一定的时间。请求出从起点到终点所需的最少时间。
输入有多组数据，不超过10组。
每组第一行一个整数N（1<=N<=100）。
第2~N+1行表示迷宫，每行有N个字符。字符# .分别代表墙壁、通道。保证起点(1,1)和终点(N,N)都是通道。字符'1'~'9'代表该区域需要逗留相应的时间来清除障碍物。
每组数据输出一行，一个整数代表从起点所需的最少时间。如果从起点不能到达终点，则输出-1。
3 .## .7. ##. 2 .# #.
11 -1
样例1解释：从起点(1,1)走到(2,2)花费2，然后花费7清理障碍物，然后走到终点(3,3)花费2，一共花费11。