T566302 「2025 YAC Round 3」芙兰也想看烟花

「2025 YAC Round 3」C 题

博丽神社准备开展烟花晚会，芙兰朵露也想去看。 在幻想乡，芙兰朵露居住在距离博丽神社遥远的红魔馆。幻想乡可以看作是一个 $n \times m$ 的网格图，红魔馆位于 $(1, 1)$，博丽神社位于 $(n, m)$。 网格图中包含 `#.X` 三种字符。其中 `#` 表示障碍物，不可行走； `.` 和 `X` 都属于空地，芙兰可以行走。 对于当前芙兰所在的位置 $(x, y)$： - 若 $(x, y)$ 为 `.`，芙兰可以消耗 $1$ 个单位时间移动至相邻的四个位置，即 $(x - 1, y)$，$(x + 1, y)$，$(x, y - 1)$，$(x, y + 1)$，前提位置合法； - 若 $(x, y)$ 为 `X`，芙兰可以消耗 $1$ 个单位时间移动到对角的四个位置，即 $(x - 1, y - 1)$，$(x + 1, y + 1)$，$(x - 1, y + 1)$，$(x + 1, y - 1)$，前提位置合法。 请问芙兰朵露从红魔馆 $(1, 1)$ 到达博丽神社 $(n, m)$ 最短需要多少单位的时间。 保证 $(1, 1)$ 和 $(n, m)$ 不是 `#`。如果无法到达，输出 $-1$。

第一行输入两个整数 $n, m$（$1\le n, m \le 500$），表示网格图大小。 接下来 $n$ 行每行输入 $m$ 个字符，如题意所示。

输出一行一个整数表示芙兰到达博丽神社所需最短时间；若无法到达，输出 $-1$。