StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's classify the cell values into <code>target value</code> and <code>replacement value(s)</code>, where the cells with <code>target value</code> are the ones you want to modify. You want to cluster the ones with <code>replacement value(s)</code>. In your example, these values happen to be 1, and (2,3) respectively.</p> <p>One usual application of flood-fill is to well, change cells with <code>replacement value(s)</code> to ones with <code>target value</code>, e.g. <em>bucket fill</em> tool in paint applications. If this is your use-case, you can simply change the cell values each time you visit the cell, thus removing the need to remember if you visited it previously. I am assuming that's not your use-case.</p> <p><strong>Method #1:</strong> Using dictionary</p> <p>I would use a dictionary with (row, col) of the visited cell as key. Since you want to see if you have visited a (row, col), you can do it in O(1) time-complexity. Your method will need to first go to the particular <code>replacement value</code> key, and then iterate through the list to find if the (current row, current col) is present in it. It's time-complexity is proportional to O(k), where k is the number of elements in the list. In the worst case, it will be O(RxC), where RxC is the dimension of the matrix.</p> <p><strong>Method #2:</strong> Using a bool matrix</p> <p>Another approach which is simple is to have a matrix of type bool with same dimensions as the cell value matrix. Each time you visit a cell, mark it as True. You can check if a cell is already visited then in O(1).</p> <p>In the worst case, both the above data structures will have a space-complexity of O(RxC). I am assuming this is fine, since you already have a matrix of the same order for cell values.</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