T635082 【五十六】四：选功法

[【五十六】历险记](https://www.luogu.com.cn/training/804406#information) 第四集： 继上一集： 56成功得到了一件趁手的武器。 接着，56打算去藏经阁选功法。不一会儿，56选好了一本五星功法《**如何正确地品尝冰红茶**》。  但是，56找不到回去的路了，所以56想请聪明帅气的你帮帮56。 因为56想在回去的路上再选一本功法，所以你要选择在**保证**是**最短路径**的同时**尽可能多**地经过书架（**可以走书架上**）。不过，路上可能会有垃圾，56是洁癖，所以不想走在垃圾上。

藏经阁是一个边长为 $N$ 的正方形，垃圾用 `#` 表示，书架用 `*` 表示，路用 `.` 表示。 56从 `(1,1)` 点出发（出发点长度为1），藏经阁的出口在 `(N,N)` 点。 因为56赶时间，所以请你帮他找到去出口的最短路径。

第一行，一个正整数 $N$ 。 下面 $N$ 行，每行 $N$ 个字符，字符只有 `#`、`*`、`.`，字符之间没有空格。

一行，共两个整数，第一个为56最多能经过的书架数，第二个为去出口的最短路径长度。

- 对于 $20\%$ 的数据， $2≤N≤10$ 。 - 对于另 $20\%$ 的数据， $2≤N≤100$ ，且仅有一条最短路径。 - 对于 $100\%$ 的数据， $2≤N≤1000$ ，保证起点与终点上没有垃圾。