StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<ol> <li><p>One condition in <code>Possibles</code> is incorrect:</p> <pre><code>/* INCORRECT: Should be [ Poz >= Leng - 1 ] */ if(Poz >= Leng) // From bottom to top { Possible[3] = 1; } </code></pre> <p>But this one is only a logical error and should not cause segmentation faults.</p></li> <li><p>It looks like you have encountered a stack overflow.</p> <p>Let's do simple calculation. For 10000 * 10000 matrix and word length of 10000, if you start calling <code>Find()</code> at the top left of the matrix, then three directions are possible. In worst case, <code>Find()</code> will traverse about 10000*3 elements. Note in <code>Func()</code> there are 3 string instances (sizeof(string) == 24 in 32bit VC2013), plus various integers. The size of a single frame could easily exceed 100 bytes. Since you are using recursive calls, this could lead to a stack usage of at least 10000 * 3 * 100 = 3000000bytes = approx. 3M.</p> <p>This number is not very large, but enough for a stack overflow since Windows has a default stack size of 1M. (<a href="http://msdn.microsoft.com/en-us/library/8cxs58a6.aspx" rel="nofollow">http://msdn.microsoft.com/en-us/library/8cxs58a6.aspx</a>)</p></li> </ol> <p><b>Advice for improvements</b></p> <p>This is my used pattern to solve this kinds of <code>matrix traversal</code> problems.</p> <p>First, define an constant array to hold offsets for movements (<a href="http://en.wikipedia.org/wiki/Moore_neighborhood" rel="nofollow">Moore neighborhood</a>):</p> <pre><code>const int delta[8][2] = { { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } }; </code></pre> <p>Second, use a single <code>for</code> to check for all directions:</p> <pre><code>int initial_x = .., initial_y = ..; for (int dir = 0; dir < 8; dir++) { for (int count = 0; count < WORD_LENGTH; count++) { int current_x = initial_x + delta[dir][0] * count; int current_y = initial_y + delta[dir][1] * count; if (IS_INVALID(current_x, current_y)) { break; } } } </code></pre> <p>Last, insert various code and flags to complete the program.</p> <p>Another hint: you can use <code>char</code> type to get and compare a single character in a string (Use <code>word[idx]</code> to get <code>idx</code>th character of <code>word</code>). This could be substantially faster than using <code>substr</code>.</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