ÿþ<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <meta http-equiv="content-type" content="text/html; charset=utf-8" /> <title>C++ code colored by C++2HTML</title> <meta name="generator" content="C++2HTML by Jasper Bedaux" /> <!-- To generate your own colored code visit http://www.bedaux.net/cpp2html/ --> <style type="text/css"> .comment { color: #999999; font-style: italic; } .pre { color: #000099; } .string { color: #009900; } .char { color: #009900; } .float { color: #996600; } .int { color: #999900; } .bool { color: #000000; font-weight: bold; } .type { color: #FF6633; } .flow { color: #FF0000; } .keyword { color: #990000; } .operator { color: #663300; font-weight: bold; } .operator { color: #663300; font-weight: bold; } </style> </head> <body> <pre><span class="comment">// Problem C: Ancient Messages // Adrian Dale // 28/10/2011 // This is version 3 of the code that uses an algorithm based on flood filling // scan lines (ie run length encoded representation of the data) // Same basic algorithm as version 1, though. // On the uva judge this finished in 0.164 seconds vs 0.248 for version one // // Update: This is actually version 3 and is identical to version two apart from // a tiny fix to re-instate the loop-skipping for 0 and f pixels. // However the submitted version showed a suspiciously high improvement going // from 0.164 to 0.076 seconds </span><span class="pre">#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;string&gt; #include &lt;sstream&gt; #include &lt;algorithm&gt; #include &lt;set&gt; #include &lt;vector&gt; #include &lt;assert.h&gt; #include &lt;Windows.h&gt; </span><span class="keyword"> using namespace</span> std<span class="operator">;</span><span class="comment"> // Timer code from Stephan T. Lavavej's Nurikabe solver </span><span class="type"> long long</span> counter<span class="operator">() {</span> LARGE_INTEGER li<span class="operator">;</span> QueryPerformanceCounter<span class="operator">(&amp;</span>li<span class="operator">);</span><span class="flow"> return</span> li<span class="operator">.</span>QuadPart<span class="operator">; }</span><span class="type"> long long</span> frequency<span class="operator">() {</span> LARGE_INTEGER li<span class="operator">;</span> QueryPerformanceFrequency<span class="operator">(&amp;</span>li<span class="operator">);</span><span class="flow"> return</span> li<span class="operator">.</span>QuadPart<span class="operator">; }</span> string format_time<span class="operator">(</span><span class="keyword">const</span><span class="type"> long long</span> start<span class="operator">,</span><span class="keyword"> const</span><span class="type"> long long</span> finish<span class="operator">) {</span> ostringstream oss<span class="operator">;</span><span class="flow"> if</span><span class="operator"> ((</span>finish<span class="operator"> -</span> start<span class="operator">) *</span><span class="int"> 1000</span><span class="operator"> &lt;</span> frequency<span class="operator">()) {</span> oss<span class="operator"> &lt;&lt; (</span>finish<span class="operator"> -</span> start<span class="operator">) *</span><span class="float"> 1000000.0</span><span class="operator"> /</span> frequency<span class="operator">() &lt;&lt;</span><span class="string"> " microseconds"</span><span class="operator">; }</span><span class="flow"> else if</span><span class="operator"> (</span>finish<span class="operator"> -</span> start<span class="operator"> &lt;</span> frequency<span class="operator">()) {</span> oss<span class="operator"> &lt;&lt; (</span>finish<span class="operator"> -</span> start<span class="operator">) *</span><span class="float"> 1000.0</span><span class="operator"> /</span> frequency<span class="operator">() &lt;&lt;</span><span class="string"> " milliseconds"</span><span class="operator">; }</span><span class="flow"> else</span><span class="operator"> {</span> oss<span class="operator"> &lt;&lt; (</span>finish<span class="operator"> -</span> start<span class="operator">) *</span><span class="float"> 1.0</span><span class="operator"> /</span> frequency<span class="operator">() &lt;&lt;</span><span class="string"> " seconds"</span><span class="operator">; }</span><span class="flow"> return</span> oss<span class="operator">.</span>str<span class="operator">(); }</span><span class="keyword"> static const</span><span class="type"> int</span> MAX_W<span class="operator"> =</span><span class="int"> 50</span><span class="operator">;</span><span class="keyword"> static const</span><span class="type"> int</span> MAX_H<span class="operator"> =</span><span class="int"> 200</span><span class="operator">;</span><span class="keyword"> typedef</span> pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type">int</span><span class="operator">&gt;</span> CoordType<span class="operator">;</span><span class="comment"> // Globals that will be set per test case </span><span class="type">int</span> W<span class="operator">;</span><span class="type"> int</span> H<span class="operator">;</span><span class="type"> int</span> CaseNum<span class="operator">;</span><span class="comment"> // Craftily initialise enough memory to hold the largest possible // test case (plus room for a border), so that we don't need to // keep new'ing and deleting memory. // The border means we don't ever need to test for pixels outside // the bitmap // This will be obsolete once the scan line algorithm works </span><span class="type">int</span> Pixels<span class="operator">[</span>MAX_W<span class="operator">*</span><span class="int">4</span><span class="operator">+</span><span class="int">2</span><span class="operator">][</span>MAX_H<span class="operator">+</span><span class="int">2</span><span class="operator">];</span><span class="keyword"> typedef</span> pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type">int</span><span class="operator">&gt;</span> RunType<span class="operator">;</span> vector<span class="operator">&lt;</span> vector<span class="operator">&lt;</span>RunType<span class="operator">&gt; &gt;</span> ScanLines<span class="operator">;</span><span class="comment"> // Map to count number of holes for each shape </span>vector<span class="operator">&lt;</span><span class="type">int</span><span class="operator">&gt;</span> VoidsMap<span class="operator">;</span><span class="comment"> // Very rough code to make a .bmp file of each of the test cases // TODO - make it big enough to show the border on the right and // bottom sides </span><span class="type">void</span> DebugBitmap<span class="operator">() {</span> ostringstream fileName<span class="operator">;</span> fileName<span class="operator"> &lt;&lt;</span><span class="string"> "bitmap"</span><span class="operator"> &lt;&lt;</span> CaseNum<span class="operator"> &lt;&lt;</span><span class="string"> ".bmp"</span><span class="operator">;</span> ofstream bmpFile<span class="operator">;</span> bmpFile<span class="operator">.</span>open<span class="operator">(</span>fileName<span class="operator">.</span>str<span class="operator">(),</span> ios<span class="operator">::</span>binary<span class="operator">);</span><span class="flow"> if</span><span class="operator"> (</span>bmpFile<span class="operator">.</span>good<span class="operator">() ==</span><span class="bool"> false</span><span class="operator">) {</span> cout<span class="operator"> &lt;&lt;</span><span class="string"> "ERROR WRITING DEBUG BITMAP"</span><span class="operator"> &lt;&lt;</span> endl<span class="operator">;</span><span class="flow"> return</span><span class="operator">; }</span><span class="type"> char</span> header<span class="operator">[]={</span><span class="int">0x42</span><span class="operator">,</span><span class="int"> 0x4d</span><span class="operator">,</span><span class="int"> 0xf9</span><span class="operator">,</span><span class="int"> 0x27</span><span class="operator">,</span><span class="int">0x02</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x1a</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0c</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">,</span><span class="int">0x0</span><span class="operator">};</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span><span class="keyword">sizeof</span><span class="operator">(</span>header<span class="operator">)/</span><span class="keyword">sizeof</span><span class="operator">(</span><span class="type">char</span><span class="operator">); ++</span>i<span class="operator">)</span> bmpFile<span class="operator"> &lt;&lt;</span> header<span class="operator">[</span>i<span class="operator">];</span><span class="comment"> // Width </span> bmpFile<span class="operator"> &lt;&lt;</span><span class="char"> '\xc8'</span><span class="operator"> &lt;&lt;</span><span class="char"> '\0'</span><span class="operator">;</span><span class="comment"> // Height </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xc8</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator">;</span><span class="comment"> // more header stuff </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x01</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x18</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">00</span><span class="operator">;</span><span class="comment"> //for(int y=0; y&lt;MAX_H; ++y) </span><span class="flow"> for</span><span class="operator">(</span><span class="type"> int</span> y<span class="operator">=</span>MAX_H<span class="operator">-</span><span class="int">1</span><span class="operator">;</span> y<span class="operator">&gt;=</span><span class="int">0</span><span class="operator">; --</span>y<span class="operator">) {</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>MAX_W<span class="operator">*</span><span class="int">4</span><span class="operator">; ++</span>x<span class="operator">) {</span><span class="flow"> if</span><span class="operator"> (</span> x<span class="operator"> &gt;=</span> W<span class="operator"> ||</span> y<span class="operator"> &gt;=</span> H<span class="operator"> ) {</span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator">; }</span><span class="flow"> else</span><span class="operator"> {</span><span class="flow"> switch</span><span class="operator">(</span> Pixels<span class="operator">[</span>x<span class="operator">][</span>y<span class="operator">] ) {</span><span class="flow"> case</span><span class="int"> 2</span><span class="operator">:</span><span class="comment"> // Border </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xFF</span><span class="operator">;</span><span class="flow"> break</span><span class="operator">;</span><span class="flow"> case</span><span class="int"> 0</span><span class="operator">:</span><span class="comment"> // White Background </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xFF</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xFF</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xFF</span><span class="operator">;</span><span class="flow"> break</span><span class="operator">;</span><span class="flow"> case</span><span class="int"> 1</span><span class="operator">:</span><span class="comment"> // Black Ink of shap </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator">;</span><span class="flow"> break</span><span class="operator">;</span><span class="flow"> case</span><span class="int"> 3</span><span class="operator">:</span><span class="comment"> // Visited Background </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0xFF</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator">;</span><span class="flow"> break</span><span class="operator">;</span><span class="flow"> default</span><span class="operator">:</span><span class="comment"> // This will be a shape pixel which (in our test cases) // can be any number from 4 to 32. // It could be more with bigger input files, of course. // We'll give each one a different shade of green </span> bmpFile<span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator"> &lt;&lt; (</span><span class="type">char</span><span class="operator">)(</span><span class="int">7</span><span class="operator">*</span>Pixels<span class="operator">[</span>x<span class="operator">][</span>y<span class="operator">]) &lt;&lt; (</span><span class="type">char</span><span class="operator">)</span><span class="int">0x00</span><span class="operator">;</span><span class="flow"> break</span><span class="operator">; }; } } }</span> bmpFile<span class="operator">.</span>close<span class="operator">(); }</span><span class="comment"> // Dump a small section of the Pixels to the screen </span><span class="type">void</span> DebugPrint<span class="operator">() {</span><span class="comment"> // Debug printing </span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> y<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> y<span class="operator">&lt;</span>min<span class="operator">(</span><span class="int">15</span><span class="operator">,</span> H<span class="operator">); ++</span>y<span class="operator">) {</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>min<span class="operator">(</span><span class="int">75</span><span class="operator">,</span> W<span class="operator">); ++</span>x<span class="operator">) {</span> cout<span class="operator"> &lt;&lt;</span> Pixels<span class="operator">[</span>x<span class="operator">][</span>y<span class="operator">]; }</span> cout<span class="operator"> &lt;&lt;</span> endl<span class="operator">; }</span> cout<span class="operator"> &lt;&lt;</span> endl<span class="operator">; }</span><span class="type"> void</span> DebugPrintScanLines<span class="operator">() {</span><span class="flow"> for</span><span class="operator">(</span>size_t i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span>ScanLines<span class="operator">.</span>size<span class="operator">(); ++</span>i<span class="operator">) {</span> vector<span class="operator">&lt;</span>RunType<span class="operator">&gt; &amp;</span>line<span class="operator"> =</span> ScanLines<span class="operator">[</span>i<span class="operator">];</span><span class="flow"> for</span><span class="operator">(</span> size_t j<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> j<span class="operator">&lt;</span>line<span class="operator">.</span>size<span class="operator">(); ++</span>j<span class="operator">) {</span> RunType rt<span class="operator"> =</span> line<span class="operator">[</span>j<span class="operator">];</span> cout<span class="operator"> &lt;&lt;</span><span class="string"> "("</span><span class="operator"> &lt;&lt;</span> rt<span class="operator">.</span>first<span class="operator"> &lt;&lt;</span><span class="string"> ","</span><span class="operator"> &lt;&lt;</span> rt<span class="operator">.</span>second<span class="operator"> &lt;&lt;</span><span class="string"> ") "</span><span class="operator">; }</span> cout<span class="operator"> &lt;&lt;</span> endl<span class="operator">; }</span><span class="flow"> for</span><span class="operator">(</span>size_t i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span>ScanLines<span class="operator">.</span>size<span class="operator">(); ++</span>i<span class="operator">) {</span> vector<span class="operator">&lt;</span>RunType<span class="operator">&gt; &amp;</span>line<span class="operator"> =</span> ScanLines<span class="operator">[</span>i<span class="operator">];</span><span class="flow"> for</span><span class="operator">(</span> size_t j<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> j<span class="operator">&lt;</span>line<span class="operator">.</span>size<span class="operator">(); ++</span>j<span class="operator">) {</span> RunType rt<span class="operator"> =</span> line<span class="operator">[</span>j<span class="operator">];</span><span class="comment"> //cout &lt;&lt; "(" &lt;&lt; rt.first &lt;&lt; "," &lt;&lt; rt.second &lt;&lt; ") "; </span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> k<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> k<span class="operator">&lt;</span>rt<span class="operator">.</span>second<span class="operator">; ++</span>k<span class="operator">)</span> cout<span class="operator"> &lt;&lt;</span> rt<span class="operator">.</span>first<span class="operator">; }</span> cout<span class="operator"> &lt;&lt;</span> endl<span class="operator">; } }</span><span class="keyword"> inline</span><span class="type"> void</span> getRealCoords<span class="operator">(</span><span class="type"> int</span> sx<span class="operator">,</span><span class="type"> int</span> sy<span class="operator">,</span><span class="type"> int</span><span class="operator"> &amp;</span>rsx<span class="operator">,</span><span class="type"> int</span><span class="operator"> &amp;</span>rex<span class="operator"> ) {</span> rsx<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> rex<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span><span class="type"> int</span> scanStart<span class="operator">=</span><span class="int">0</span><span class="operator">;</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> s<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> s<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>sy<span class="operator">].</span>size<span class="operator">(); ++</span>s<span class="operator">) {</span> rsx<span class="operator"> =</span> scanStart<span class="operator">;</span> rex<span class="operator"> =</span> rsx<span class="operator"> +</span> ScanLines<span class="operator">[</span>sy<span class="operator">][</span>s<span class="operator">].</span>second<span class="operator"> -</span><span class="int"> 1</span><span class="operator">;</span><span class="flow"> if</span><span class="operator"> (</span>s<span class="operator"> &gt;=</span> sx<span class="operator">)</span><span class="flow"> break</span><span class="operator">;</span> scanStart<span class="operator"> +=</span> ScanLines<span class="operator">[</span>sy<span class="operator">][</span>s<span class="operator">].</span>second<span class="operator">; }</span><span class="comment"> //cout &lt;&lt; rsx &lt;&lt; " " &lt;&lt; rex &lt;&lt; endl; </span><span class="operator">}</span><span class="type"> bool</span> readTestCaseOLD<span class="operator">() {</span><span class="type"> int</span> pixH<span class="operator"> =</span> H<span class="operator">+</span><span class="int">2</span><span class="operator">;</span><span class="type"> int</span> pixW<span class="operator"> =</span> W<span class="operator">*</span><span class="int">4</span><span class="operator">+</span><span class="int">2</span><span class="operator">;</span><span class="comment"> // First set up a Pixel border </span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>pixW<span class="operator">; ++</span>x<span class="operator">) {</span> Pixels<span class="operator">[</span>x<span class="operator">][</span><span class="int">0</span><span class="operator">] =</span><span class="int"> 2</span><span class="operator">;</span> Pixels<span class="operator">[</span>x<span class="operator">][</span>pixH<span class="operator">-</span><span class="int">1</span><span class="operator">] =</span><span class="int"> 2</span><span class="operator">; }</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> y<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> y<span class="operator">&lt;</span>pixH<span class="operator">-</span><span class="int">1</span><span class="operator">; ++</span>y<span class="operator">) {</span> Pixels<span class="operator">[</span><span class="int">0</span><span class="operator">][</span>y<span class="operator">] =</span><span class="int"> 2</span><span class="operator">;</span> Pixels<span class="operator">[</span>pixW<span class="operator">-</span><span class="int">1</span><span class="operator">][</span>y<span class="operator">] =</span><span class="int"> 2</span><span class="operator">; }</span><span class="comment"> // Read in the rows and unpack the hex digits // into our Pixels grid </span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> i<span class="operator">=</span><span class="int">1</span><span class="operator">;</span> i<span class="operator">&lt;</span>pixH<span class="operator">-</span><span class="int">1</span><span class="operator">; ++</span>i<span class="operator">) {</span> string row<span class="operator">;</span> cin<span class="operator"> &gt;&gt;</span> row<span class="operator">;</span><span class="comment"> // Start inside the border </span><span class="type"> int</span> pixx<span class="operator">=</span><span class="int">1</span><span class="operator">;</span><span class="flow"> for</span><span class="operator">(</span>size_t j<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> j<span class="operator">&lt;</span>row<span class="operator">.</span>size<span class="operator">(); ++</span>j<span class="operator">) {</span><span class="type"> char</span> cell<span class="operator"> =</span> row<span class="operator">[</span>j<span class="operator">];</span><span class="comment"> // Convert character to numeric value </span><span class="flow"> if</span><span class="operator"> (</span> cell<span class="operator"> &gt;=</span><span class="char"> '0'</span><span class="operator"> &amp;&amp;</span> cell<span class="operator"> &lt;=</span><span class="char"> '9'</span><span class="operator">)</span> cell<span class="operator"> -=</span><span class="char"> '0'</span><span class="operator">;</span><span class="flow"> else</span> cell<span class="operator"> =</span> cell<span class="operator"> -</span><span class="char"> 'a'</span><span class="operator"> +</span><span class="int"> 10</span><span class="operator">;</span> Pixels<span class="operator">[</span>pixx<span class="operator">++][</span>i<span class="operator">] = (</span>cell<span class="operator"> &amp;</span><span class="int"> 0x08</span><span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">;</span> Pixels<span class="operator">[</span>pixx<span class="operator">++][</span>i<span class="operator">] = (</span>cell<span class="operator"> &amp;</span><span class="int"> 0x04</span><span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">;</span> Pixels<span class="operator">[</span>pixx<span class="operator">++][</span>i<span class="operator">] = (</span>cell<span class="operator"> &amp;</span><span class="int"> 0x02</span><span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">;</span> Pixels<span class="operator">[</span>pixx<span class="operator">++][</span>i<span class="operator">] = (</span>cell<span class="operator"> &amp;</span><span class="int"> 0x01</span><span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">; } }</span><span class="comment"> // Set W to the width in Pixels as this will // be easier to work with </span> W<span class="operator"> =</span> W<span class="operator">*</span><span class="int">4</span><span class="operator"> +</span><span class="int"> 2</span><span class="operator">;</span> H<span class="operator"> +=</span><span class="int"> 2</span><span class="operator">;</span><span class="flow"> return</span><span class="bool"> true</span><span class="operator">; }</span><span class="keyword"> inline</span><span class="type"> int</span> CellToInt<span class="operator">(</span><span class="type">char</span> cell<span class="operator">) {</span><span class="comment"> // Convert character to numeric value </span><span class="flow"> if</span><span class="operator"> (</span> cell<span class="operator"> &gt;=</span><span class="char"> '0'</span><span class="operator"> &amp;&amp;</span> cell<span class="operator"> &lt;=</span><span class="char"> '9'</span><span class="operator">)</span> cell<span class="operator"> -=</span><span class="char"> '0'</span><span class="operator">;</span><span class="flow"> else</span> cell<span class="operator"> =</span> cell<span class="operator"> -</span><span class="char"> 'a'</span><span class="operator"> +</span><span class="int"> 10</span><span class="operator">;</span><span class="flow"> return</span> cell<span class="operator">; }</span><span class="type"> bool</span> readTestCaseIntoScanLines<span class="operator">() {</span><span class="comment"> // Assuming H and W have been read in </span> ScanLines<span class="operator">.</span>clear<span class="operator">();</span><span class="comment"> // We know how many rows there are in image, although we won't know how many // runs of pixels there are on each line until we read them </span> ScanLines<span class="operator">.</span>reserve<span class="operator">(</span>H<span class="operator">);</span><span class="comment"> // Read in the rows and unpack them into Scan Lines </span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span>H<span class="operator">; ++</span>i<span class="operator">) {</span> string row<span class="operator">;</span> cin<span class="operator"> &gt;&gt;</span> row<span class="operator">;</span> vector<span class="operator">&lt;</span>RunType<span class="operator">&gt;</span> line<span class="operator">;</span><span class="type"> int</span> pixx<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span><span class="comment"> // See what the first pixel of the row is </span><span class="type"> int</span> currentPix<span class="operator"> = (</span>CellToInt<span class="operator">(</span>row<span class="operator">[</span><span class="int">0</span><span class="operator">]) &amp;</span><span class="int"> 0x80</span><span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">;</span><span class="flow"> for</span><span class="operator">(</span>size_t j<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> j<span class="operator">&lt;</span>row<span class="operator">.</span>size<span class="operator">(); ++</span>j<span class="operator">) {</span><span class="type"> char</span> cell<span class="operator"> =</span> CellToInt<span class="operator">(</span>row<span class="operator">[</span>j<span class="operator">]);</span><span class="type"> int</span> bit<span class="operator"> =</span><span class="int"> 0x08</span><span class="operator">;</span><span class="flow"> while</span><span class="operator">(</span>bit<span class="operator"> &gt;</span><span class="int"> 0</span><span class="operator">) {</span><span class="type"> int</span> pix<span class="operator">;</span><span class="comment"> // next pixel </span> pix<span class="operator"> = (</span>cell<span class="operator"> &amp;</span> bit<span class="operator">) !=</span><span class="int"> 0</span><span class="operator"> ?</span><span class="int"> 1</span><span class="operator"> :</span><span class="int"> 0</span><span class="operator">;</span><span class="flow"> if</span><span class="operator"> (</span> pix<span class="operator"> ==</span> currentPix<span class="operator"> ) {</span><span class="comment"> // Extend the current scanline </span><span class="flow"> if</span><span class="operator"> (</span>cell<span class="operator"> ==</span><span class="int"> 0</span><span class="operator"> ||</span> cell<span class="operator"> ==</span><span class="int"> 15</span><span class="operator">) {</span><span class="comment"> // Minor optimisation to save us another three // runs round this loop in the common case of // solid run of pixels in the input // Saves us about 10ms off the total run time </span> pixx<span class="operator">+=</span><span class="int">4</span><span class="operator">;</span> bit<span class="operator"> =</span><span class="int"> 0x01</span><span class="operator">;</span><span class="comment"> // exit while loop early </span><span class="operator"> }</span><span class="flow"> else</span><span class="operator"> ++</span>pixx<span class="operator">; }</span><span class="flow"> else</span><span class="operator"> {</span><span class="comment"> // Start a new scanline // cout &lt;&lt; "(" &lt;&lt; currentPix &lt;&lt; "," &lt;&lt; pixx &lt;&lt; ") "; </span> line<span class="operator">.</span>push_back<span class="operator">(</span> make_pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type"> int</span><span class="operator">&gt;(</span>currentPix<span class="operator">,</span> pixx<span class="operator">) );</span><span class="flow"> if</span><span class="operator"> (</span>cell<span class="operator">==</span><span class="int">0</span><span class="operator"> ||</span> cell<span class="operator"> ==</span><span class="int"> 15</span><span class="operator">) {</span> pixx<span class="operator"> =</span><span class="int"> 4</span><span class="operator">;</span> bit<span class="operator"> =</span><span class="int"> 0x01</span><span class="operator">; }</span><span class="flow"> else</span> pixx<span class="operator">=</span><span class="int">1</span><span class="operator">;</span> currentPix<span class="operator"> =</span> pix<span class="operator">; }</span> bit<span class="operator"> &gt;&gt;=</span><span class="int"> 1</span><span class="operator">; } }</span><span class="comment"> // scanline ends at end of row </span> line<span class="operator">.</span>push_back<span class="operator">(</span> make_pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type"> int</span><span class="operator">&gt;(</span>currentPix<span class="operator">,</span> pixx<span class="operator">) );</span><span class="comment"> //cout &lt;&lt; "(" &lt;&lt; currentPix &lt;&lt; "," &lt;&lt; pixx &lt;&lt; ") " &lt;&lt; endl; </span> ScanLines<span class="operator">.</span>push_back<span class="operator">(</span>line<span class="operator">); }</span><span class="comment"> // Set W to the width in Pixels as this will // be easier to work with // TODO - may not actually be needed with scan line algorithms </span> W<span class="operator"> =</span> W<span class="operator">*</span><span class="int">4</span><span class="operator">;</span><span class="flow"> return</span><span class="bool"> true</span><span class="operator">; }</span><span class="comment"> // Here sy is the row number and sx is the Run number in that row </span><span class="type">int</span> floodFill_ScanLines<span class="operator">(</span><span class="type"> int</span> sx<span class="operator">,</span><span class="type"> int</span> sy<span class="operator">,</span><span class="type"> int</span> searchCol<span class="operator">,</span><span class="type"> int</span> fillCol<span class="operator"> ) {</span><span class="type"> int</span> lastTouched<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span><span class="comment"> // CoordType is the coords of the Run, NOT the pixel </span> set<span class="operator">&lt;</span>CoordType<span class="operator">&gt;</span> unvisited<span class="operator">;</span> unvisited<span class="operator">.</span>insert<span class="operator">(</span> make_pair<span class="operator">(</span>sx<span class="operator">,</span> sy<span class="operator">) );</span><span class="flow"> while</span><span class="operator">(</span>unvisited<span class="operator">.</span>empty<span class="operator">() ==</span><span class="bool"> false</span><span class="operator">) {</span><span class="comment"> // Remove the first item from the unvisited set and inspect it </span> CoordType vc<span class="operator"> = *</span>unvisited<span class="operator">.</span>begin<span class="operator">();</span> unvisited<span class="operator">.</span>erase<span class="operator">(</span> unvisited<span class="operator">.</span>begin<span class="operator">() );</span> RunType<span class="operator"> &amp;</span>run<span class="operator"> =</span> ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator">][</span>vc<span class="operator">.</span>first<span class="operator">];</span><span class="flow"> if</span><span class="operator"> (</span>run<span class="operator">.</span>first<span class="operator"> ==</span> searchCol<span class="operator">) {</span><span class="comment"> // If the pixel at this coord is the colour we're looking for, // then fill it with the fill colour and push all of the // adjacent pixels that match the search colour into the set, // so that they can be searched in turn. // Using set so that I don't have to care about pushing the same // pixel more than once. </span> run<span class="operator">.</span>first<span class="operator"> =</span> fillCol<span class="operator">;</span><span class="comment"> // lastTouched is whatever colour our left or right neighbouring run is // We only care about this value for internal voids, so it shouldn't matter // if we have single run scanlines and don't populate last touched here </span><span class="flow"> if</span><span class="operator"> (</span>vc<span class="operator">.</span>first<span class="operator"> &gt;</span><span class="int"> 0</span><span class="operator">)</span> lastTouched<span class="operator"> =</span> ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator">][</span>vc<span class="operator">.</span>first<span class="operator">-</span><span class="int">1</span><span class="operator">].</span>first<span class="operator">;</span><span class="flow"> if</span><span class="operator"> (</span>vc<span class="operator">.</span>first<span class="operator"> &lt;</span> ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator">].</span>size<span class="operator">()-</span><span class="int">1</span><span class="operator">)</span> lastTouched<span class="operator"> =</span> ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator">][</span>vc<span class="operator">.</span>first<span class="operator">+</span><span class="int">1</span><span class="operator">].</span>first<span class="operator">;</span><span class="comment"> // Need to locate all adjoining scan lines and push into unvisited list // - get actual x coords of start and end of our run </span><span class="type"> int</span> xstart<span class="operator">,</span> xend<span class="operator">;</span> getRealCoords<span class="operator">(</span>vc<span class="operator">.</span>first<span class="operator">,</span> vc<span class="operator">.</span>second<span class="operator">,</span> xstart<span class="operator">,</span> xend<span class="operator">);</span><span class="comment"> // Only need to search above and below - no need to worry about horizontal neighbours, // although we'll need to know these to update lastTouched </span><span class="flow"> if</span><span class="operator"> (</span>vc<span class="operator">.</span>second<span class="operator"> &gt;</span><span class="int"> 0</span><span class="operator">)</span><span class="comment"> // Check we're not on top row </span><span class="operator"> {</span><span class="comment"> // Search above for all segments that overlap the one we're searching </span><span class="flow"> for</span><span class="operator">(</span>size_t srch<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> srch<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator"> -</span><span class="int"> 1</span><span class="operator">].</span>size<span class="operator">(); ++</span>srch<span class="operator">) {</span><span class="type"> int</span> sstart<span class="operator">,</span> send<span class="operator">;</span> getRealCoords<span class="operator">(</span>srch<span class="operator">,</span> vc<span class="operator">.</span>second<span class="operator">-</span><span class="int">1</span><span class="operator">,</span> sstart<span class="operator">,</span> send<span class="operator">);</span><span class="flow"> if</span><span class="operator"> ( (</span>sstart<span class="operator"> &lt;=</span> xstart<span class="operator"> &amp;&amp;</span> send<span class="operator"> &gt;=</span> xstart<span class="operator">) || (</span>sstart<span class="operator"> &lt;=</span> xend<span class="operator"> &amp;&amp;</span> send<span class="operator"> &gt;=</span> xstart<span class="operator">) ) {</span><span class="comment"> //overlap </span> unvisited<span class="operator">.</span>insert<span class="operator">(</span> make_pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type">int</span><span class="operator">&gt;(</span>srch<span class="operator">,</span> vc<span class="operator">.</span>second<span class="operator">-</span><span class="int">1</span><span class="operator">) ); } } }</span><span class="flow"> if</span><span class="operator"> (</span>vc<span class="operator">.</span>second<span class="operator"> &lt;</span> H<span class="operator">-</span><span class="int">1</span><span class="operator">)</span><span class="comment"> // Check we're not on top row </span><span class="operator"> {</span><span class="comment"> // TODO - fix this horrible duplicated code. // Am planning to replace this method soon, anyway // Search above for all segments that overlap the one we're searching </span><span class="flow"> for</span><span class="operator">(</span>size_t srch<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> srch<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>vc<span class="operator">.</span>second<span class="operator"> +</span><span class="int"> 1</span><span class="operator">].</span>size<span class="operator">(); ++</span>srch<span class="operator">) {</span><span class="type"> int</span> sstart<span class="operator">,</span> send<span class="operator">;</span> getRealCoords<span class="operator">(</span>srch<span class="operator">,</span> vc<span class="operator">.</span>second<span class="operator">+</span><span class="int">1</span><span class="operator">,</span> sstart<span class="operator">,</span> send<span class="operator">);</span><span class="flow"> if</span><span class="operator"> ( (</span>sstart<span class="operator"> &lt;=</span> xstart<span class="operator"> &amp;&amp;</span> send<span class="operator"> &gt;=</span> xstart<span class="operator">) || (</span>sstart<span class="operator"> &lt;=</span> xend<span class="operator"> &amp;&amp;</span> send<span class="operator"> &gt;=</span> xstart<span class="operator">) ) {</span><span class="comment"> //overlap </span> unvisited<span class="operator">.</span>insert<span class="operator">(</span> make_pair<span class="operator">&lt;</span><span class="type">int</span><span class="operator">,</span><span class="type">int</span><span class="operator">&gt;(</span>srch<span class="operator">,</span> vc<span class="operator">.</span>second<span class="operator">+</span><span class="int">1</span><span class="operator">) ); } } }</span><span class="comment"> //int pix = Pixels[vc.first + DX[i]][vc.second + DY[i]]; //if ( pix == searchCol ) // unvisited.insert( make_pair(vc.first + DX[i], vc.second + DY[i]) ); //else if (pix != fillCol) // lastTouched = pix; </span><span class="operator"> } }</span><span class="flow"> return</span> lastTouched<span class="operator">; }</span><span class="comment"> // Direction offsets in x and y, so we can process each direction // with a single set of instructions in a loop </span><span class="type">int</span> DX<span class="operator">[] = {</span><span class="int">0</span><span class="operator">,</span><span class="int"> 1</span><span class="operator">,</span><span class="int"> 0</span><span class="operator">, -</span><span class="int">1</span><span class="operator">};</span><span class="type"> int</span> DY<span class="operator">[] = {-</span><span class="int">1</span><span class="operator">,</span><span class="int"> 0</span><span class="operator">,</span><span class="int"> 1</span><span class="operator">,</span><span class="int"> 0</span><span class="operator">};</span><span class="comment"> // Starting from (sx,sy) flood fill all pixels that are colour searchCol // with colour fillCol. // Function will return the colour of a pixel that borders a visited // pixel that differs from the searchCol. This will only give reliable results // once all the exterior background and shapes have been coloured. // It is used so we can work out which spaces belong to which shape </span><span class="type">int</span> floodFill<span class="operator">(</span><span class="type"> int</span> sx<span class="operator">,</span><span class="type"> int</span> sy<span class="operator">,</span><span class="type"> int</span> searchCol<span class="operator">,</span><span class="type"> int</span> fillCol<span class="operator"> ) {</span><span class="type"> int</span> lastTouched<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> set<span class="operator">&lt;</span>CoordType<span class="operator">&gt;</span> unvisited<span class="operator">;</span> unvisited<span class="operator">.</span>insert<span class="operator">(</span> make_pair<span class="operator">(</span>sx<span class="operator">,</span> sy<span class="operator">) );</span><span class="flow"> while</span><span class="operator">(</span>unvisited<span class="operator">.</span>empty<span class="operator">() ==</span><span class="bool"> false</span><span class="operator">) {</span><span class="comment"> // Remove the first item from the unvisited set and inspect it </span> CoordType vc<span class="operator"> = *</span>unvisited<span class="operator">.</span>begin<span class="operator">();</span> unvisited<span class="operator">.</span>erase<span class="operator">(</span> unvisited<span class="operator">.</span>begin<span class="operator">() );</span><span class="flow"> if</span><span class="operator"> (</span>Pixels<span class="operator">[</span>vc<span class="operator">.</span>first<span class="operator">][</span>vc<span class="operator">.</span>second<span class="operator">] ==</span> searchCol<span class="operator">) {</span><span class="comment"> // If the pixel at this coord is the colour we're looking for, // then fill it with the fill colour and push all of the // adjacent pixels that match the search colour into the set, // so that they can be searched in turn. // Using set so that I don't have to care about pushing the same // pixel more than once. // TODO - would stack be faster, and simply not care about this issue? </span> Pixels<span class="operator">[</span>vc<span class="operator">.</span>first<span class="operator">][</span>vc<span class="operator">.</span>second<span class="operator">] =</span> fillCol<span class="operator">;</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span><span class="keyword">sizeof</span><span class="operator">(</span>DX<span class="operator">)/</span><span class="keyword">sizeof</span><span class="operator">(</span><span class="type">int</span><span class="operator">); ++</span>i<span class="operator">) {</span><span class="type"> int</span> pix<span class="operator"> =</span> Pixels<span class="operator">[</span>vc<span class="operator">.</span>first<span class="operator"> +</span> DX<span class="operator">[</span>i<span class="operator">]][</span>vc<span class="operator">.</span>second<span class="operator"> +</span> DY<span class="operator">[</span>i<span class="operator">]];</span><span class="flow"> if</span><span class="operator"> (</span> pix<span class="operator"> ==</span> searchCol<span class="operator"> )</span> unvisited<span class="operator">.</span>insert<span class="operator">(</span> make_pair<span class="operator">(</span>vc<span class="operator">.</span>first<span class="operator"> +</span> DX<span class="operator">[</span>i<span class="operator">],</span> vc<span class="operator">.</span>second<span class="operator"> +</span> DY<span class="operator">[</span>i<span class="operator">]) );</span><span class="flow"> else if</span><span class="operator"> (</span>pix<span class="operator"> !=</span> fillCol<span class="operator">)</span> lastTouched<span class="operator"> =</span> pix<span class="operator">; } } }</span><span class="flow"> return</span> lastTouched<span class="operator">; }</span><span class="comment"> // This function checks off all 0 pixels visitable from the edge // of the image. These pixels are therefore outside of any shapes // in the image. </span><span class="type">void</span> fillBackground<span class="operator">() {</span><span class="comment"> // Scan along top and bottom edges flood filling from any // 0 pixel we find. Use value 3 to denote background </span><span class="flow"> for</span><span class="operator">(</span> size_t x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>ScanLines<span class="operator">[</span><span class="int">0</span><span class="operator">].</span>size<span class="operator">(); ++</span>x<span class="operator">)</span><span class="flow"> if</span><span class="operator"> (</span>ScanLines<span class="operator">[</span><span class="int">0</span><span class="operator">][</span>x<span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 0</span><span class="operator">)</span> floodFill_ScanLines<span class="operator">(</span>x<span class="operator">,</span><span class="int">0</span><span class="operator">,</span><span class="int">0</span><span class="operator">,</span><span class="int">3</span><span class="operator">);</span><span class="flow"> for</span><span class="operator">(</span> size_t x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>H<span class="operator">-</span><span class="int">1</span><span class="operator">].</span>size<span class="operator">(); ++</span>x<span class="operator">)</span><span class="flow"> if</span><span class="operator"> (</span>ScanLines<span class="operator">[</span>H<span class="operator">-</span><span class="int">1</span><span class="operator">][</span>x<span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 0</span><span class="operator">)</span> floodFill_ScanLines<span class="operator">(</span>x<span class="operator">,</span>H<span class="operator">-</span><span class="int">1</span><span class="operator">,</span><span class="int">0</span><span class="operator">,</span><span class="int">3</span><span class="operator">);</span><span class="comment"> // Same for left and right edges </span><span class="flow"> for</span><span class="operator">(</span> size_t y<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> y<span class="operator">&lt;</span>ScanLines<span class="operator">.</span>size<span class="operator">(); ++</span>y<span class="operator">) {</span><span class="flow"> if</span><span class="operator"> (</span>ScanLines<span class="operator">[</span>y<span class="operator">][</span><span class="int">0</span><span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 0</span><span class="operator">)</span> floodFill_ScanLines<span class="operator">(</span><span class="int">0</span><span class="operator">,</span>y<span class="operator">,</span><span class="int">0</span><span class="operator">,</span><span class="int">3</span><span class="operator">);</span> size_t rhs<span class="operator"> =</span> ScanLines<span class="operator">[</span>y<span class="operator">].</span>size<span class="operator">()-</span><span class="int">1</span><span class="operator">;</span><span class="flow"> if</span><span class="operator"> (</span>ScanLines<span class="operator">[</span>y<span class="operator">][</span>rhs<span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 0</span><span class="operator">)</span> floodFill_ScanLines<span class="operator">(</span>rhs<span class="operator">,</span>y<span class="operator">,</span><span class="int">0</span><span class="operator">,</span><span class="int">3</span><span class="operator">); } }</span><span class="comment"> // Flood fill all of the shapes we can find. // Mark each one in the pixel map with a unique number, // starting from 3 which was the number used to denote pixels // in the background outside the shapes // Return a count of how many shapes we spot. </span><span class="type">int</span> fillShapes<span class="operator">() {</span><span class="type"> int</span> ShapeNo<span class="operator"> =</span><span class="int"> 3</span><span class="operator">;</span><span class="comment"> // Scan entire grid looking for 1 pixels </span><span class="flow"> for</span><span class="operator">(</span> size_t y<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> y<span class="operator">&lt;</span>ScanLines<span class="operator">.</span>size<span class="operator">(); ++</span>y<span class="operator">) {</span><span class="flow"> for</span><span class="operator">(</span> size_t x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>y<span class="operator">].</span>size<span class="operator">(); ++</span>x<span class="operator">) {</span><span class="flow"> if</span><span class="operator"> (</span> ScanLines<span class="operator">[</span>y<span class="operator">][</span>x<span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 1</span><span class="operator"> ) {</span><span class="comment"> // If we find a 1 pixel that means we've got a // shape we haven't yet visited, so fill it with the // ShapeNo </span><span class="operator"> ++</span>ShapeNo<span class="operator">;</span> floodFill_ScanLines<span class="operator">(</span>x<span class="operator">,</span> y<span class="operator">,</span><span class="int"> 1</span><span class="operator">,</span> ShapeNo<span class="operator">); } } }</span><span class="flow"> return</span> ShapeNo<span class="operator">-</span><span class="int">3</span><span class="operator">; }</span><span class="comment"> // Fill in the centres of each shape. // For each one, note which shape it touches // and keep a count of how many holes touch each shape. // ShapesFound says how many shapes to expect </span><span class="type">void</span> fillVoids<span class="operator">(</span><span class="type">int</span> ShapesFound<span class="operator">) {</span> VoidsMap<span class="operator">.</span>clear<span class="operator">();</span><span class="flow"> if</span><span class="operator"> (</span>ShapesFound<span class="operator"> ==</span><span class="int"> 0</span><span class="operator">)</span><span class="flow"> return</span><span class="operator">;</span><span class="comment"> // Because VoidsMap is empty it'll get resized to the // desired size with each entry initialised to zero </span> VoidsMap<span class="operator">.</span>resize<span class="operator">(</span>ShapesFound<span class="operator">,</span><span class="int"> 0</span><span class="operator">);</span><span class="comment"> // Scan entire grid looking for remaining 0 pixels </span><span class="flow"> for</span><span class="operator">(</span> size_t y<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> y<span class="operator">&lt;</span>ScanLines<span class="operator">.</span>size<span class="operator">(); ++</span>y<span class="operator">) {</span><span class="flow"> for</span><span class="operator">(</span> size_t x<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> x<span class="operator">&lt;</span>ScanLines<span class="operator">[</span>y<span class="operator">].</span>size<span class="operator">(); ++</span>x<span class="operator">) {</span><span class="flow"> if</span><span class="operator"> (</span> ScanLines<span class="operator">[</span>y<span class="operator">][</span>x<span class="operator">].</span>first<span class="operator"> ==</span><span class="int"> 0</span><span class="operator"> ) {</span><span class="type"> int</span> lastTouched<span class="operator"> =</span> floodFill_ScanLines<span class="operator">(</span>x<span class="operator">,</span> y<span class="operator">,</span><span class="int"> 0</span><span class="operator">,</span><span class="int"> 2</span><span class="operator">);</span> assert<span class="operator">(</span>lastTouched<span class="operator"> &lt;=</span> ShapesFound<span class="operator">);</span><span class="flow"> if</span><span class="operator"> (</span>lastTouched<span class="operator"> &gt;</span><span class="int"> 3</span><span class="operator">) ++</span>VoidsMap<span class="operator">[</span>lastTouched<span class="operator">-</span><span class="int">4</span><span class="operator">]; } } } }</span><span class="type"> void</span> outputResults<span class="operator">() {</span><span class="comment"> // Hieroglyphs in order from 0 to 5 of how many holes they have </span><span class="type"> char</span> hieroglyphs<span class="operator">[]={</span><span class="char">'W'</span><span class="operator">,</span><span class="char">'A'</span><span class="operator">,</span><span class="char">'K'</span><span class="operator">,</span><span class="char">'J'</span><span class="operator">,</span><span class="char">'S'</span><span class="operator">,</span><span class="char">'D'</span><span class="operator">};</span> string results<span class="operator">;</span><span class="flow"> for</span><span class="operator">(</span> size_t i<span class="operator">=</span><span class="int">0</span><span class="operator">;</span> i<span class="operator">&lt;</span>VoidsMap<span class="operator">.</span>size<span class="operator">(); ++</span>i<span class="operator">) {</span><span class="type"> int</span> holeCount<span class="operator"> =</span> VoidsMap<span class="operator">[</span>i<span class="operator">];</span> results<span class="operator">.</span>push_back<span class="operator">(</span>hieroglyphs<span class="operator">[</span>holeCount<span class="operator">]); }</span> sort<span class="operator">(</span> results<span class="operator">.</span>begin<span class="operator">(),</span> results<span class="operator">.</span>end<span class="operator">() );</span> cout<span class="operator"> &lt;&lt;</span><span class="string"> "Case "</span><span class="operator"> &lt;&lt;</span> CaseNum<span class="operator"> &lt;&lt;</span><span class="string"> ": "</span><span class="operator"> &lt;&lt;</span> results<span class="operator"> &lt;&lt;</span> endl<span class="operator">; }</span><span class="type"> bool</span> nextTestCase<span class="operator">() {</span> cin<span class="operator"> &gt;&gt;</span> H<span class="operator">;</span> cin<span class="operator"> &gt;&gt;</span> W<span class="operator">;</span><span class="flow"> if</span><span class="operator"> (</span>H<span class="operator">==</span><span class="int">0</span><span class="operator"> &amp;&amp;</span> W<span class="operator">==</span><span class="int">0</span><span class="operator">)</span><span class="flow"> return</span><span class="bool"> false</span><span class="operator">;</span><span class="comment"> //readTestCase(); </span> readTestCaseIntoScanLines<span class="operator">();</span> fillBackground<span class="operator">();</span><span class="type"> int</span> ShapesFound<span class="operator"> =</span> fillShapes<span class="operator">();</span> fillVoids<span class="operator">(</span>ShapesFound<span class="operator">);</span><span class="comment"> //DebugPrintScanLines(); </span> outputResults<span class="operator">(); ++</span>CaseNum<span class="operator">;</span><span class="flow"> return</span><span class="bool"> true</span><span class="operator">; }</span><span class="type"> void</span> Run<span class="operator">() {</span><span class="pre"> #ifdef _DEBUG </span> cout<span class="operator"> &lt;&lt;</span><span class="string"> "WARNING: DEBUG BUILD"</span><span class="operator"> &lt;&lt;</span> endl<span class="operator">;</span><span class="comment"> // Switch so we read our input from a file. // Means I don't have to set up a command line in visual studio to // run with the debugger </span> streambuf<span class="operator"> *</span>backup<span class="operator">, *</span>psbuf<span class="operator">;</span> ifstream filestr<span class="operator">;</span><span class="comment"> //filestr.open("ancient.in"); </span> filestr<span class="operator">.</span>open<span class="operator">(</span><span class="string">"test3.txt"</span><span class="operator">);</span> backup<span class="operator"> =</span> cin<span class="operator">.</span>rdbuf<span class="operator">();</span> psbuf<span class="operator"> =</span> filestr<span class="operator">.</span>rdbuf<span class="operator">();</span> cin<span class="operator">.</span>rdbuf<span class="operator">(</span>psbuf<span class="operator">);</span><span class="pre"> #endif </span> CaseNum<span class="operator">=</span><span class="int">1</span><span class="operator">;</span><span class="type"> bool</span> moreTests<span class="operator">=</span><span class="bool">true</span><span class="operator">;</span><span class="flow"> while</span><span class="operator">(</span>moreTests<span class="operator">) {</span><span class="keyword"> const</span><span class="type"> long long</span> start<span class="operator"> =</span> counter<span class="operator">();</span> moreTests<span class="operator"> =</span> nextTestCase<span class="operator">();</span><span class="keyword"> const</span><span class="type"> long long</span> finish<span class="operator"> =</span> counter<span class="operator">();</span><span class="comment"> //cout &lt;&lt; "Case " &lt;&lt; CaseNum &lt;&lt; " took " &lt;&lt; format_time(start, finish) &lt;&lt; endl; </span><span class="operator"> }</span><span class="pre"> #ifdef _DEBUG </span><span class="comment"> // Put our input stream back to normal // Not terribly important if we're about to exit anyway! </span> cin<span class="operator">.</span>rdbuf<span class="operator">(</span>backup<span class="operator">);</span> filestr<span class="operator">.</span>close<span class="operator">();</span><span class="pre"> #endif </span><span class="operator">}</span><span class="type"> int</span><span class="keyword"> main</span><span class="operator">() {</span><span class="keyword"> const</span><span class="type"> long long</span> start<span class="operator"> =</span> counter<span class="operator">();</span> Run<span class="operator">();</span><span class="keyword"> const</span><span class="type"> long long</span> finish<span class="operator"> =</span> counter<span class="operator">();</span><span class="comment"> // NB Remove this line before submitting to judge! </span> cout<span class="operator"> &lt;&lt;</span><span class="string"> "Total Run Time: "</span><span class="operator"> &lt;&lt;</span> format_time<span class="operator">(</span>start<span class="operator">,</span> finish<span class="operator">) &lt;&lt;</span> endl<span class="operator">;</span><span class="flow"> return</span><span class="int"> 0</span><span class="operator">; }</span></pre> </body> </html>