Databases
StackOverflow2013
Postsdbo
POBacktracking solution for programming exercise (fitting pipes)
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBacktracking solution for programming exercise (fitting pipes)
    text
    copied!<p>I'm reviewing a programming problem from a local programming contest.</p> <p>You can download the problem <a href="http://www.vlaamseprogrammeerwedstrijd.be/2011/opgaves/cat2-2011/loodgieter.pdf" rel="nofollow noreferrer">here</a> (pdf). It's in dutch but the pictures will help to understand it.</p> <p>You receive a m*m grid as input with some pipes and some missing spots (the questionmarks). The remaining pipes have to be placed in the grid so that they connect with the others.</p> <p>Each pipe is represented as a letter (see picture on page 2). The letter 'A' has value 1, 'B' has value 2, ..</p> <p>I tried solving it with backtracking (it doesn't quite work yet). But since the grid can be 10x10 this will be too slow. Can someone suggest a better (faster) solution/approach?</p> <pre><code>#include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;vector&gt; using namespace std; #define sz(a) int((a).size()) #define pb push_back int m, found; string letters; vector&lt;int&gt; done; vector&lt;string&gt; a; int ok(char letter, int c, int r) { int val = letter - 'A' + 1; //checking if no side goes outside if (r == 0 &amp;&amp; (val &amp; 1)) return 0; if (r == m - 1 &amp;&amp; (val &amp; 4)) return 0; if (c == 0 &amp;&amp; (val &amp; 8)) return 0; if (c == m - 1 &amp;&amp; (val &amp; 2)) return 0; //check if the side is connected the other pipe on the grid if (r &gt; 0 &amp;&amp; a[r - 1][c] != '?' &amp;&amp; (a[r - 1][c] &amp; 4) &amp;&amp; !(val &amp; 1)) return 0; if (c &gt; 0 &amp;&amp; a[r][c - 1] != '?' &amp;&amp; (a[r][c - 1] &amp; 2) &amp;&amp; !(val &amp; 8)) return 0; if (r &lt; m - 1 &amp;&amp; a[r + 1][c] != '?' &amp;&amp; (a[r + 1][c] &amp; 1) &amp;&amp; !(val &amp; 4)) return 0; if (c &lt; m - 1 &amp;&amp; a[r][c + 1] != '?' &amp;&amp; (a[r][c + 1] &amp; 8) &amp;&amp; !(val &amp; 2)) return 0; return 1; } void solve(int num_placed, int pos) { if (found) return; //done if (num_placed == sz(letters)) { for (int i = 0; i &lt; m; ++i) cout &lt;&lt; a[i] &lt;&lt; endl; found = 1; return; } int c = pos % m; int r = pos / m; if (a[r][c] != '?') solve(num_placed, pos + 1); //try all the pipes on this position for (int i = 0; i &lt; sz(letters); ++i) { if (!done[i] &amp;&amp; ok(letters[i], c, r)) { a[r][c] = letters[i]; done[i] = 1; solve(num_placed + 1, pos + 1); done[i] = 0; a[r][c] = '?'; } } } int main() { freopen("input.txt", "r", stdin); int n; cin &gt;&gt; n; while (n--) { cin &gt;&gt; m; cin &gt;&gt; letters; cout &lt;&lt; m &lt;&lt; endl; a.clear(); for (int i = 0; i &lt; m; ++i) { string line; cin &gt;&gt; line; a.pb(line); } done = vector&lt;int&gt;(sz(letters), 0); found = 0; solve(0, 0); } return 0; } </code></pre>
 

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