The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a magic wand which you can use $k$ times to destroy a wall. How do we find the shortest path from the top left corner to the bottom right?

  • 1
    $\begingroup$ Please add a reference to the original question. Always. Always. Always. (If it does not make sense, do tell people why. For example, the source is behind a paywall. Even in that case, mention that paywall and its location, since some people might have access to it.) $\endgroup$ – John L. Jun 12 at 16:53
  • $\begingroup$ Would you be happy with an algorithm having a time complexity of $O(kn)$? $\endgroup$ – Steven Jun 12 at 17:12
  • $\begingroup$ @Steven Yes, sure. $\endgroup$ – user821 Jun 12 at 17:17
  • $\begingroup$ Nice exercise! However, we discourage posts that are the statement of an exercise-style task and a request for us to solve it for you. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jun 12 at 17:40

Let $w$ be the width of the grid and $h$ be its height. Let $n = w \cdot h$. The following solution requires $O(n k)$ time and works regardless of whether there are restrictions on the direction of movement. If the movement is allowed only downwards and rightwards then there is a solution with a running time of $O(n)$, which is better whenever $k$ is not a constant (see Nir Shahar's answer).

Assume that there is no wall on the upper-left cell (otherwise remove it, and decrease $k$ by $1$).

Construct a directed graph $G$ as follows: the vertex set $V=\{1,\dots,h\} \times \{1, \dots, w\}$ consists of $n$ nodes. A generic node $(i,j) \in V$ represent the cell in the $i$-th row and $j$-th column of the grid.

There is an edge between vertex $u$ to vertex $v$ iff it is possible to move (in one step) from cell $u$ to cell $v$ without breaking a wall on $v$. If all directions of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is no wall on $v$.

Create a directed graph $H$ consisting of $k+1$ copies $G_0, G_1, \dots, G_k$ of $G$. Intuitively the $i$-th copy represents the situation in which exactly $i$ walls have been broken.

Augment $H$ as follows: for each $i=0, \dots, k-1$ add an edge from vertex $u$ of the $i$-th copy to vertex $v$ of the $(i+1)$-th copy iff it is possible to move (in one step) from cell $u$ to cell $v$ but this requires breaking a wall on $v$. Again, if all direction of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is a wall on $v$.

Finally, add a new vertex $t$ and all the edges from vertices $(\ell, \ell)$ in all of the $k+1$ copies of $G$ to $t$. Notice that the number of vertices is $O(nk)$ and that the number of edges is linear in the number of vertices.

It now suffices to find a shortest path $P = \langle v_0, v_1, \dots, v_h \rangle$ from vertex $(0,0)$ in $G_0$ to $t$. This can be done in time $O(nk)$ using, e.g., a breadth first search from $(0, 0)$ in $G_0$. The sought shortest path on the grid has length $h$ and is obtained by traversing the cells corresponding to vertices $v_0$ to $v_{h-1}$.

| cite | improve this answer | |
  • $\begingroup$ This solution is not optimal though $\endgroup$ – nir shahar Jun 12 at 18:08
  • $\begingroup$ What do you mean not optimal? Are you referring to the running time or the length of the returned path? I can prove that the length of the returned path is optimal. $\endgroup$ – Steven Jun 12 at 18:08
  • $\begingroup$ The running time. You can also add a version of any pathfinding algorithm (like Dijkstra's algorithm) to reduce the running time a little bit to $O(n\times min\{k,log(n)\})$ $\endgroup$ – nir shahar Jun 12 at 18:26
  • $\begingroup$ Although i suppose the running time of $O(nk)$ is enough $\endgroup$ – nir shahar Jun 12 at 18:27
  • 2
    $\begingroup$ Nice answer! This solution solves, in fact, the more general problem of the shortest at-most-$k$-wall-breaking path in a directed graph with walls. $\endgroup$ – John L. Jun 12 at 19:02

Note: This solution assumes you cannot move left or up.

Have you heard about dynamic programming? With a little bit of work, Im pretty sure it can help you find a solution for the question!

An actual solution (using dynamic programming. Please, try to do it yourself first):

let $m$ be the board width (or height). Then $n=m^2$.

Build an empty matrix $M$ of size $m\times m$.

Now, run the following algorithm:

  1. For $i$ from $m$ to 1:
    1. For $j$ from $m$ to 1:
      1. Set $M[i,j] = min\{M[i+1,j],M[i,j+1]\} + C$ where $C=k$ if there is a wall and $C=1$ otherwise. (also $M[m+1,j]=0=M[i,m+1]$)

This matrix will contain the costs of the shortest paths between the node $(i,j)$ to the bottom right. To find the actual path, just traverse the lowest valued path between $(0,0)$ and $(m,m)$ in the matrix.

This will cost $O(m^2)=O(n)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.