StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Actually you may consider that the elevation of the destination square can't be changed either, since there's no need to elevate it.</p> <p>Now, in classical Dijkstra(-like) algorithm you'd say that every square of your grid has a <em>price</em> at which you can reach this square. That is, your source square has <em>price</em>=0, Then in a loop you take the next <em>cheapest</em> square and try to move from it to all the adjacent squares, whose price is bigger.</p> <p>In your problem you have an extra degree of freedom: the elevation level of your square. That is, when you move to a square you are allowed to change its height.</p> <p>The most straightforward "brute-force" solution would be the following:</p> <ol> <li>Check all the cells, build a set of their elevation levels (i.e. the spectrum of all the heights). Say you have <strong>H</strong> distinct heights.</li> <li>Define the state of the square as its position <strong>and</strong> height. The define your problem in terms of Dijkstra graph.</li> <li>For every square add a vertex to the graph that represents its actual elevation. Then add extra vertexes that represent it with a bigger elevation (besides source and destination squares). So that you have up to <strong>H</strong> vertexes for every square.</li> <li>Define an <em>internal price</em> of every vertex as its height above its actual position. So that for every square you have a vertex with <em>internal price</em>=0 (the actual elevation), plus number of vertexes representing elevated positions with appropriate <em>internal price</em>.</li> <li>Connected vertexes representing neighbor squares by <strong>directed</strong> edges. Put an edge only if the source vertex has an elevation at least of the target vertex.</li> </ol> <p>Then find the shortest path by Dijkstra (or A*) algorithm. The <em>cost</em> of the move is considered the <em>internal price</em> of the target vertex (our edges don't carry the price).</p> <p>In simple words we've built a "layered" graph, each layer corresponds to an optional height. At each position you're allowed to make a move either at your current layer, or get lower.</p> <p>Needless to say that the problem complexity increases. The vertex count is increased by the factor of (up to) <strong>H</strong>, the same holds for the edges count.</p> <p>Basically the path-search has the complexity of <code>log(N) * N * M</code> where <strong>N</strong> is squares cell count, and <strong>M</strong> - is the connectivity orders (number of connected nearest neighbors). After your inflation the complexity grows by (up to) the factor of <strong>H^2</strong>.</p> <p>So that the efficiency of this algorithm depends on the number of distinct heights. If you have a small number of heights - the algorithm should be efficient. However if all your squares have distinct heights - perhaps another approach should be used.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload