0

行*列グリッドがあり、グリッド上の各ノードに整数（状態）値があるとします。

state[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]

の値が

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

この2点から同じ状態だけで構成された「パス」があるかどうかを確認したい。

パスとは、左、右、下、または上の状態が元の状態と同じであることを意味します。

重要かどうかはわかりませんが、状態がバイナリ（＃または-）であるとしましょう。したがって、state == "-"のパスをチェックしている場合、状態がNになったら、パスを続行できます。 E、S、Wも== "-"

終了行は開始行と同じである必要があります。

成功例：

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

また

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

また

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

失敗の例：

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

また

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

また

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

失敗します。

どうすればよいですか？私はObjectiveCでコーディングしていますが、手順を理解するのに役立つ擬似コードで十分です。

パスのBOOL存在をチェックすることに加えて、パス内のすべてのグリッド座標の配列を返したいと思います。

これは実装が簡単ですか、それとも私は頭を悩ませていますか？

4

2 に答える 2

0

非常に一般的な一般的なプログラミングの問題の特定のケースを見ているようです。グリッドは特定のタイプのグラフです。各セルは、隣接するノードに接続できるノードです。最も単純なグラフ走査戦略を確認することから始めます。幅優先または深さ優先検索。これらの2つのアルゴリズムは、この特定の問題を解決するために必要なすべての問題に精通している必要がある単純なツールです。あなたの場合、検索を制限して、現在のノードと等しい値を含むノードのみを探索し、目的地に到達できるかどうかを確認することができます。

これで、これらのアルゴリズムのいずれかがパスが存在するかどうかを教えてくれます。それは良いスタートですが、最短経路を見つけたい場合はどうでしょうか？そのために、ダイクストラのアルゴリズムがあります。

これはかなり良いことですが、最短経路を見つけるためにグラフ全体をトラバースする必要があります。グラフが小さい場合は問題ありませんが、グラフが大きくなると、コストのかかる操作になります。どこでも検索せずに最短経路を見つける方法はありますか？あります：A *（「Aスター」）アルゴリズムを見てください。

于 2013-03-09T05:41:54.743 に答える
0

これが私からうまくいった解決策です-@Florisによってリンクされた迷路解決アルゴリズムに基づいています。

バグが1つか2つある可能性があり、それは確かに最適化されていませんが、今のところは機能します。

みんなの助けに感謝して、フォローするのはかなり簡単なはずです：

-(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 に答える