T441776 电子鼠迷宫（Hard Version）

一个电子鼠正望向坐标 $\color{red}(x,y)$ 处的奶酪，它想吃到那个奶酪。

一只电子鼠可移动动 $\color{green}8$ 个方向，分别是$\color{red}上，下，左，右，左上，左下，右上，右下$，他们分为$\color{red}直着走$和$\color{red}斜着走$，其中： - 直着走需要花 $\color{green}2$ 秒，例：从 $\color{red}(1,1)$ 走到 $\color{red}(1,2)$ 要花 $\color{green}2$ 秒。 - 斜着走需要花 $\color{green}3$ 秒，例：从 $\color{red}(1,1)$ 走到 $\color{red}(2,2)$ 要花 $\color{green}3$ 秒。 一个迷宫一共有 $\color{blue}n \times m(2 \le n,m \le 100)$ 个格子，其中`@`代表$\color{red}电子鼠$，`%`代表$\color{orange}奶酪$，`#`代表$\color{green}墙$，`.`代表$\color{blue}空地$。 问电子鼠最早花几秒可以吃到奶酪，如果吃不道则输出`-1`。

第一行 $\color{green}n,m$ 空格间隔。 接下来 $\color{green}n$ 行 $\color{green}m$ 个数，包含`@`，`%`，`#`，`.`四个字符。

输出电子鼠$\color{red}最早$可以吃到奶酪的秒数，如果吃不到，则输出`-1`。

#### 样例 $1$ 解释 $\color{green}3$ 秒路径为：$\color{green}(1,1)>(2,2)$。 #### 样例 $2$ 解释 因为电子鼠被墙围起来了，没有路可以走，所以输出 $\color{green}-1$。 #### 数据点 Subtask #$\color{green}0$ $\color{red}样例$ $\color{green}1$，$\color{green}0$ 分。 Subtask #$\color{green}1$ $\color{red}0\le n,m \le 5$，其中电子鼠在 $\color{green}(1,1)$ 处，奶酪在 $\color{green}(n,m)$ 处，每个测试点 $\color{green}10$ 分，$\color{green}2$ 个测试点，$\color{red}没有墙$。 Subtask #$\color{green}2$ $\color{red}0\le n,m \le 5$，其中电子鼠在 $\color{green}(1,1)$ 处，奶酪在 $\color{green}(n,m)$ 处，每个测试点 $\color{green}15$ 分，$\color{green}2$ 个测试点，$\color{red}有墙$。 Subtask #$\color{green}3$ $\color{red}0\le n,m \le 50$，每个测试点 $\color{green}20$ 分，$\color{green}2$ 个测试点。 Subtask #$\color{green}4$ $\color{red}无特殊要求$，每个测试点 $\color{green}10$ 分，$\color{green}1$ 个测试点。 #### 后记 灵感来源：[电子鼠迷宫竞赛](https://baike.baidu.com/item/%E5%85%A8%E5%9B%BD%E7%94%B5%E8%84%91%E9%BC%A0%E8%B5%B0%E8%BF%B7%E5%AE%AB%E7%AB%9E%E8%B5%9B/8337490?fr=ge_ala)。