CODEWITHSUNDEEP
javaalgorithm
user1810925
user1810925

Reputation: 63

How to find a path of true values connecting the borders of a 2D array of false values

I need to traverse a 2D array of boolean values, from top border to bottom border, and determine a path made entirely of true values. At this point, I have tried many different techniques, but I haven't made any progress. Could anyone help me out here?

Here's an example: 

false true  true  false false false
false true  false false false false
false true  true  false false false
false false true  false false false

I need to find a way to determine the true value along the borders, then find a way to traverse the path of true values.

#..###
#.####
#..###
##.###

I have begun with algorithms at this point. I have thought of traversing the columns and searching for a true value, incrementing the rows by one and then searching the last row, but I don't know how to go about the first and last columns.

The first part to the problem is determining the location of a true value along the border. The second part is finding the path of the true values and recording their coordinates.

Upvotes: 2

Views: 726

Answers (2)

ashley
ashley

Reputation: 1175

You can turn it into a graph and run a path finding algorithm.

Turn every matrix entry into a node on the graph. for each true node positioned at [i,j] of matrix, connect it to every one of the closest four neighbor entries with true values, i.e., the entries at [i+/-1, j] and [i, j+/-1] whenever such an entry is true. These are all and only edges on the graph. Then run Dijkstra algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm on all true nodes positioned at top border. Returns you the shortest path between each true node pair whenever there is such a path.

Upvotes: 1

Pops
Pops

Reputation: 30828

This could be solved through a simple trial and error algorithm. The top-to-bottom requirement is nice because you know you have to start on the top row of the array, so all you have to do is search that one row for true values to start off.

Once you find a true, look at its neighboring cells. (Exactly which neighboring cells depends on whether diagonals count and whether your path can bend back upwards like the trap pipes under a sink.)

enter image description here

(image from Wikipedia)

If you find another cell containing true, then that cell becomes your "current" cell, and you look at its neighbors. Keep doing this until you reach a true cell in the last row. Or, if you don't find any true neighbors, then go back up to the previous cell and continue with its neighbors.

One way of doing this uses recursion and very little code. Just do something like

// pseudocode only
for(Cell foo : all cells in top row)
    checkCell(foo);

boolean checkCell(Cell current) {
    if(current == false)
        return false;

    if(current == true && current.isInLastRow == true)
        return true;

    // if we reach here, the cell is true but we're not done
    for(Cell foo : all valid neighbors of this cell except the "parent")
        return checkCell(foo);
}

Another way uses more memory, but is also more efficient. Create a second array, of the same size as the original. When you test a cell from the original array, mark its corresponding cell in the new array. Then, when you're testing neighbors, check the new array to see if you've already been to a given neighbor. If you have, skip it, because it can't lead to success (you know this because you would have already completed and returned if it could). This could save you a lot of time if the array contains a lot of true values next to each other, like

F T T T F
F T T T F
F T T T F
F T T T F
F T T T F

EDIT:
I missed your update comment that says you need to record the coordinates of the cells in the path. No problem: just create a stack of Point objects recording where you've been. If you ever end up going down a wrong path, just pop once from the stack every time you go "back up a level."

Upvotes: 3

Related Questions