P2298 Mzc and the Male Servants' Game

The second installment of mzc and djn.

Mzc’s family is very rich (just kidding). He has $n$ male servants (those who did the first installment already know). He gathered them together, and they decided to play hide-and-seek. Now mzc is going to search for his male servants. Let’s help out! Since there are not many male servants, and mzc is very good at finding people, each time he only needs to find one male servant.

The first line contains two integers $n$ and $m$, indicating there are $n$ rows and $m$ columns where the male servants can hide. Then follow $n$ lines with $m$ columns forming a matrix: `m` denotes mzc, `d` denotes a male servant, `#` denotes an impassable cell, and `.` denotes an empty cell.

A single line. If there is a solution: output one integer $sum$, which is the minimal number of moves to find a male servant. If there is no solution: output `No Way!`.

$3 \leq m,n \leq 2000$. Because mzc is in a great hurry, he can only wait for 1 s. Translated by ChatGPT 5