0

假设我有一个行*列网格，网格上的每个节点都有一个整数（状态）值。

state[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]

如果值

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

我想检查是否存在仅由这两点相同状态组成的“路径”..

通过路径，我的意思是左侧、右侧、底部或顶部的状态与原始状态相同。

我不确定它是否重要，但可以说状态是二进制的（# 或 -）所以如果我正在检查状态 ==“-”的路径，如果状态到 N，我们可以继续路径， E,S,W 也是 == "-"

结束行必须等于开始行。

成功案例：

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

或者

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

或者

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

失败的例子：

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

或者

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

或者

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

会失败。

我该怎么做呢？我在 Objective C 中编写代码，但帮助我理解这些步骤的伪代码就足够了。

除了检查路径是否存在 BOOL 之外，我还想返回路径中所有网格坐标的数组。

这很容易实现还是我有点过头了？

4

2 回答 2

0

所以这是对我有用的解决方案——基于@Floris 链接的迷宫求解算法。

可能有一两个错误，它肯定没有优化，但它现在可以工作。

应该很容易理解，感谢大家的帮助：

-(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;
                }
            }
        }
    }
}

谢谢！

于 2013-03-10T15:09:23.293 回答
0

听起来您正在查看一个非常常见的一般编程问题的特定案例。您的网格是一种特定类型的图表；每个单元是一个节点，可以连接到相邻节点。从最简单的图遍历策略开始；广度优先或深度优先搜索。这两种算法是您应该熟悉的简单工具，也是解决此特定问题所需的全部问题。在您的情况下，您可以将搜索限制为只能探索包含与当前节点相同值的节点，并查看您是否能够到达目的地。

现在，这些算法中的任何一个都会告诉您路径是否存在。这是一个好的开始，但如果您想找到最短路径怎么办？为此，我们有Dijkstra 算法。

这很好，但我们仍然必须遍历整个图才能找到最短路径。如果图很小，这不是问题，但随着它的增长，这将成为一项昂贵的操作。有没有什么方法可以找到最短路径而不用到处搜索？有：看看A*（“A星”）算法。

于 2013-03-09T05:41:54.743 回答