StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>When dealing with this kind of problems, the first thing to do is to find a representation of the <em>state</em> of your problem. In this case, you need:</p> <ol> <li>Two integers which represents the top-left position of your figure</li> <li>One boolean which represents the color of the figure (red/blue)</li> <li>One boolean which represents the orientation of the figure (horizontal/vertical)</li> </ol> <p>If you are familiar with bitmasks, you should use just a 32 bit integer to do this (8 bits for x position, 8 bits for y position, 2 bits for the rest). In this way you don't need to implement a comparison operator. <strong>OR</strong> You define a simple struct (call it <code>state</code>) with these 3 information and a strict-ordering comparison on this (this is only needed to put <code>state</code> in <code>std::set</code>.</p> <p>After this, you can solve this problem using a <a href="http://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow">BFS</a>.</p> <p>To do that, you need:</p> <ol> <li>An <code>std::map<state,state></code> to store the position you already visited in the key, and the position you came from in the value (replace <code>map</code> with <code>unordered_map</code> if you can use c++11 and you use a bitmask to store your state)</li> <li>A <code>std::queue<state></code> in which push and pop up the states to be processed.</li> <li>Some code to determine every possible state reachable from a given one (i.e. implements all the possible moves, taking care of the board dimension)</li> </ol> <p>Pseudo code:</p> <pre><code> map<state,state> visited; queue<state> to_be_processed; visited.insert( initial_state,initial_state); //you are not coming from anywhere to_be_processed.push ( initial_state); while(!to_be_processed.empty()) { state cur = to_be_processed.pop(); if ( cur == end_state) //you are done { //to get the path from initial_state to end_state you have just to walk visited in the inverse order. return 1; } for ( i = every possible state reachable from cur) { if (visited.count(i) != 0) continue; //already visited to_be_processed.push(i); visited.insert(i,cur); //i has been visited, and you reached i from cur } } return 0; //if you get here, no way </code></pre> <p>The presence of obstacles make just the problem more difficult to code, but is no conceptually different.</p> <p>Note that in this case BFS works because the cost you pay for going from one state to another is always the same. </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