We require the knowledge of BFS (Breadth-First Search). An introduction of BFS might be found in an article by drken (in Japanese). The simplest form of BFS on a grid can be practiced in ABC007 - C (where problem statement is provided in Japanese).

As the first observation, a medicine disappears when used, but it does not need to be taken account; because in this problem, even if medicine can be used multiple times, the actions after using it the last time can be done after using it for the first time instead.

Solution 1

When a medicine is used, the position and energy right after using it is unique. Thus, the problem can be solved by constructing a \(N\)-vertex directed graph that has an edge from \(i\) to \(j\) \(\iff\) one can reach medicine \(j\) right after using medicine \(i\), and performing BFS on it.

To determine if one can reach medicine \(j\) after using medicine \(i\) without using any other medicine, it is sufficient to find the shortest distance from the position of medicine \(i\) with BFS. By performing BFS from each of the \(N\) medicines, it costs \(O(HWN)\). (By \(N \leq HW\), this is the bottleneck.)

The implementation can be simplified by placing medicine \((N+1)\) at the goal position if there is not.

Sample code (C++)

Solution 2

(Although not directly applied to our final solution, as a typical technique) one can also apply vertex doubling.

Consider the following state as a single vertex \((i, j, k)\): you are at cell \((i, j)\) with energy \(k\). Add edges as follows:

• For all \((i, j, k) \ (k \geq 1)\), add edges \((i + 1, j, k - 1), (i, j + 1, k - 1), (i - 1, j, k - 1), (i, j - 1, k - 1)\) if it points at an empty cell.
• For all medicines \(i \ (1 \leq i \leq N)\) and \(k\), add edges from \((R_i, C_i, k)\) to \((R_i, C_i, E_i)\).

One can solve the problem by performing BFS on this graph and check if the goal is reachable, but the complexity accumulates to \(\Theta((HW)^2)\) at worst.

The key to reduce the complexity is to notice that there are only at most \(N \leq 1000\) medicines. After using a medicine, we only need to consider the shortest path toward the other cells, so there are at most \(N\) distinct values for the energy for each cell. Instead of performing BFS on a graph where vertices are explicitly multiplexed, one can manage a two-dimensional array where \(d_{i, j} := \) maximum energy when reaching \((i, j)\), as in the sample code, so that the complexity is reduced to \(O(HWN)\) by this observation.

Sample code (C++)

Although we could not prove that the complexity has actually reduced, the solution that uses a priority queue runs very fast against the test cases that we prepared. Sample code (C++)