P2644 Platinum Lotus Pond

To entertain and exercise the cows, Farmer John built a beautiful pond. This rectangular pond is divided into $M$ rows and $N$ columns of cells ($1 \le M, N \le 30$). Some cells contain surprisingly sturdy lotus, some are rocks, and the rest are beautiful, pure, deep-blue water that might even hide treasure. Bessie is practicing ballet. She stands on a lotus and wants to jump to another lotus. She can only jump from one lotus to another; she cannot land on water or rocks. Bessie’s steps are like a knight in chess: each time she either moves one cell horizontally and then two cells vertically, or two cells vertically and then one cell horizontally. At most, Bessie has eight possible move directions. John has been watching Bessie’s ballet practice and noticed that sometimes she cannot reach the destination because some lotus leaves are missing. So he wants to add some lotus to help Bessie complete the task, and of course, lotus cannot be planted on rocks.

However! When planting lotus, John discovered something interesting: some cells cannot have lotus planted directly. The reason is… to be honest, the soil in those cells contains a lot of genuine platinum, which hinders lotus growth! Coincidentally, John has just learned how to mine platinum and has the tools for it, and he also found that after mining the platinum, the cell can be planted with lotus normally, without worrying about missing soil. (Because Bessie is eager to practice, John will not mine a platinum cell unless he also intends to plant a lotus there.) Mining platinum is tiring, just like planting lotus. Each action consumes $1$ point of stamina (that is, turning a platinum cell into a lotus cell requires $2$ points of stamina). John initially has $P$ points of stamina to plant lotus or mine platinum. Please help John compute the least stamina needed to help Bessie complete the task, denoted by $S$, and the number of ways to spend exactly that stamina to help Bessie, denoted by $W_S$. Since more platinum is better, also compute, among all solutions that spend $S$ stamina and help Bessie, the maximum amount of platinum that can be mined, denoted by $G$, and the number of ways to help Bessie while spending $S$ stamina and mining exactly $G$ pieces of platinum, denoted by $W_G$. If it is impossible to help Bessie within $P$ points of stamina, output only `-1`. If it is impossible to mine any platinum within $S$ points of stamina, then output only `-1` on the second line.

The first line: three integers separated by spaces: $P$, $M$, and $N$. Lines $2$ to $M+1$: the $(i+1)$-th line contains $N$ integers separated by spaces, describing the state of row $i$ of the pond: $0$ means water, $1$ means lotus, $2$ means rock, $3$ means Bessie’s starting cell, $4$ means Bessie’s destination, and $5$ means a platinum deposit.

The first line: two integers separated by a space, $S$ and $W_S$ (the minimum stamina required and the number of methods to achieve it; if it is impossible to help Bessie within $P$ stamina, output `-1`). The second line: two integers separated by a space, $G$ and $W_G$ (the maximum amount of platinum mined under the minimum-stamina condition and the number of methods to achieve it; if no platinum can be mined within $S$ stamina, output `-1` on the second line). If the first line is `-1`, do not output the second line. All output numbers are guaranteed not to exceed `long long`.

John might make a small profit by mining the platinum, but if he uses extra stamina to mine platinum without planting lotus on those cells, Bessie will be very angry! Translated by ChatGPT 5