Finding a path in a 2d grid and returning all matched nodes

Question

Say I have an rows*columns grid, and each node on the grid has an integer (state) value.

state[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]

If the value of

state[row][0] == state[row][NUMBER_OF_COLUMNS -1]

I want to check if there is a "path" consisting of only the same state from these two points..

By path, I mean the state to the left, right, bottom, or top is the same as the origin state.

I'm not sure if it matters, but lets say the state is binary (# or -) So if I'm checking for a path of state == "-", we can continue the path if the state to the N,E,S,W is also == "-"

The end row must equal the start row.

Examples of success:

|# # # # #|    
|# # # # #|    
|# # # # #|
|- # # # #|
|- - - - -|

or

|# # # # #|
|# # # - #|
|# - - - #|
|- - # - -|
|# # # - -|

or

|# # # # #|
|# # # - #|
|# # # - #|
|- - - - #|
|- # # - -|

Examples of fail:

|# # # # #|
|# # # # #|
|# # # # #|
|- - - - #|
|# # - - -|

or

|# # # # #|
|# # # - #|
|# # # - #|
|# - - - #|
|- # # - #|

or

|# # # # #|
|# # - # #|
|# # # # #|
|# - # - #|
|- # - # -|

would fail.

How do I do this? I code in Objective C, but pseudo code to help me understand the steps will be sufficient.

Besides checking for the BOOL existence of a path, I'd want to return an array of all grid coordinate in the path..

Is this easy to implement or am I in way over my head?

Answer 1

So here's the solution that worked from me - based off the maze solving algorithm linked to by @Floris.

There may be a bug or two, and it's certainly not optimized, but it works for now.

Should be pretty easy to follow, thanks for everyone's help:

-(BoardState)solutionPathExistsForColor {
    //create a board copy where the last column equals the first

    for (int i = 0; i < BOARD_ROWS+1; i++) {
        for (int j = 0; j < BOARD_COLUMNS+1; j++) {
            if (j == BOARD_COLUMNS) {
                loopedBoard[i][j] = landed[i][0];
            } else {
                loopedBoard[i][j] = landed[i][j];
            }
        }
    }

    for (BoardState state = 1; state < kBoardStateCount; state++) {
        //first check if it is possible there is a path


        //for each row
        for (int row = 0; row < BOARD_ROWS; row++) {

            //set solution path to zero
            for (int i = 0; i < BOARD_ROWS; i++) {
                for (int j = 0; j < BOARD_COLUMNS; j++) {
                    solutionPath[i][j] = 0;
                }
            }
            BOOL aTest = [self findPathToGoalRow:row //iterate
                                   andGoalColumn:BOARD_COLUMNS  //always the same
                                         fromRow:row  //iterate
                                       andColumn:0  // always the same
                                         ofState:state]; //iterate
            if (aTest) {
                CCLOG(@"Success! State %i", (int)state);
                //now that you know a path exists, modify the path to contain all correct adjacent cells
                [self fixSolutionPathOfColor:state];
                return state;
            } else {
                CCLOG(@"Failure!");
            }
        }
    }
    return kBoardStateVOID;
}

-(BOOL)findPathToGoalRow:(int)goalRow
           andGoalColumn:(int)goalColumn
                 fromRow:(int)fromRow
               andColumn:(int)fromColumn
                 ofState:(BoardState)state {


    //check to see if we've already seen this row and column
    if (solutionPath[fromRow][fromColumn] == 1) {
        return NO;
    }

//  if (x,y outside maze) return false
    if (fromRow > BOARD_ROWS -1 || fromColumn > BOARD_COLUMNS || fromRow < 0 || fromColumn < 0) {
        return NO;
    }
//  if (x,y is goal) return true
    if (fromRow == goalRow && fromColumn == goalColumn) {
        return YES;
    }
//  if (x,y not open) return false
    //if ([self boardStateAtRow:fromRow andColumn:fromColumn] != state) {
    if (loopedBoard[fromRow][fromColumn]!=state) {
        return NO;
    }


//  mark x,y as part of solution path
    solutionPath[fromRow][fromColumn] = 1;

//  if (FIND-PATH(North of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow+1
                      andColumn:fromColumn
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(East of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow
                      andColumn:fromColumn+1
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(South of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow-1
                      andColumn:fromColumn
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(West of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow
                      andColumn:fromColumn-1
                        ofState:state]) {
        return YES;
    }
//  unmark x,y as part of solution path
    solutionPath[fromRow][fromColumn] = 0;
    return NO;
}

-(void)fixSolutionPathOfColor:(BoardState)color {

    for (int column = 0; column < BOARD_COLUMNS; column++) {
        BOOL bottomColumnOfSolutionPathFound = NO;
        int checkingRow = 0;
        while (!bottomColumnOfSolutionPathFound) {
            if ([self solutionCellAtRow:checkingRow andColumn:column] == 1) {
                bottomColumnOfSolutionPathFound = YES;
            } else {
                checkingRow++;
            }
        }

        //you'll start with this bottom row and look below
        if (solutionPath[checkingRow][column] == 1) {
            int nextRowToCheck = checkingRow-1;
            BOOL keepChecking = YES;
            while (nextRowToCheck >= 0 && keepChecking) {
                if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
                    if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
                        solutionPath[nextRowToCheck][column] = 1;
                    }
                    nextRowToCheck--;
                } else {
                    keepChecking = NO;
                }
            }
            //now repeat for above
            nextRowToCheck = checkingRow+1;
            keepChecking = YES;
            while (nextRowToCheck < BOARD_ROWS && keepChecking) {
                if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
                    if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
                        solutionPath[nextRowToCheck][column] = 1;
                    }
                    nextRowToCheck++;
                } else {
                    keepChecking = NO;
                }
            }
        }
    }
}

Thanks!