P1683 Beginner

Not everyone can enter Peach Blossom Island. Huang Yaoshi hates dull people like Guo Jing. So he built a small path at the island’s only entrance, paved entirely with square tiles. Some tiles are safe to step on, while others will spray deadly poison gas the moment you step on them—you die immediately; we consider them unsafe. You can move from a safe tile to any of its four neighboring tiles, but the destination must also be safe. Because you are a friend of Huang Rong, she tells you in advance which tiles are safe and which are unsafe, and she will guide you to fly onto the first tile (the first tile may be at any safe position). Now she tells you the secret to entering Peach Blossom Island: if you can walk over the maximum number of tiles without dying, the island gate will open automatically, and you can fly straight into the gate from your current position. Note: You may revisit tiles, but you must not count the same tile more than once.

The first line contains two positive integers $W$ and $H$, denoting the width and height of the path. The following $H$ lines form an $H \times W$ character matrix. Each character represents one tile. `.` denotes a safe tile, `#` denotes an unsafe tile, and `@` denotes the first tile.

Output one line containing a single integer: the maximum number of tiles you can safely visit starting from the first tile (including the first tile).

Constraints For all test points, it is guaranteed that $1 \leq W, H \leq 20$. Translated by ChatGPT 5