First, we notice that we can fire a portal to which we will enter just before entering it - standing next to any wall, we can fire a portal and walk into it. So if we want to know how long it takes to travel to the portal we just fired, we just have to compute the distance to the nearest wall block. To do that efficiently, we can do a breadth-first search from all wall blocks to each open square. But we can avoid that by noticing that we can fire a portal from which we want to exit after walking towards or from it until the nearest wall is directly in one of the four directions (up, left, down and right). Hence we can assume that it is only worth firing two portals from the same square, then going to one of them and exiting to the other one.

So we can compute the minimum time to reach the cake by performing Dijkstra's algorithm, in which we can go from each open square to adjacent open squares with distance 1, and to four open squares next to which we can fire portals, with distance minimum of distances to walk to walls behind them. To compute their locations and distances to them efficiently, we can go through the map before performing Dijkstra, looking for the already-computed location of the required square from the adjacent square in the corresponding direction.

Complexity - ~\mathcal O(RC)~ or ~\mathcal O(RC \log(RC))~.

Subtask 1

Breadth-first search with storing both portal's positions.

Complexity - ~\mathcal O((RC)^3)~.

Subtask 3

Assuming that there is at least one wall block adjacent to each open square, after firing a portal, we can fire a portal to a wall adjacent to us and enter it. So the solution in this case is breadth-first search, in which from each open square, we can go to adjacent open squares as well as four open squares next to which we can fire portals.

Complexity - ~\mathcal O(RC)~ or ~\mathcal O(RC(R+C))~ (depends on whether we have precomputed where to fire portals).

Subtask 2

If we only notice that we can fire one portal just before entering it, we can do a breadth-first search, storing the position of one portal.

Complexity - ~\mathcal O((RC)^2)~.

Subtask 4

Same as the full solution, just without precomputing where to fire portals.

Complexity - ~\mathcal O(RC(R+C))~.