0

迷路から抜け出す可能性のあるすべてのパスを見つけるために、次の C プログラムを開発しました。そして、迷路の各部屋を通過する必要があります。私が渡している 8*7 配列の場合、54 の空き部屋があるため、'54' がその時点でハードコードされているのはそのためです。私はこれを解決し、書き直すときに動的に渡します。ただし、コードをより効率的にする方法についての助けを探しています.渡された迷路を完了するために300,000以上の可能なパスが見つかりましたが、ほぼ1時間実行されました.

#include <stdio.h>

#define FALSE 0
#define TRUE 1
#define NROWS 8
#define MCOLS 7

// Symbols:
//  0 = open
// 1 = blocked
// 2 = start
// 3 = goal
// '+' = path

char maze[NROWS][MCOLS] = {

    "2000000",
    "0000000",
    "0000000",
    "0000000",
    "0000000",
    "0000000",
    "0000000",
    "3000011"

};

int find_path(int x, int y, int c, int *t);

int main(void)
{   

    int t = 0;

    if ( find_path(0, 0, 0, &t) == TRUE )
        printf("Success!\n");
    else
        printf("Failed\n");

    return 0;

}

int find_path(int x, int y, int c, int *t)
{
    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return FALSE;

    c++;
    char oldMaze = maze[y][x];

    if ( maze[y][x] == '3' && c == 54) 
    {
        *t = *t+1;
        printf("Possible Paths are %i\n", *t);
        return FALSE;
    }

    if ( maze[y][x] != '0' && maze[y][x] != '2' ) return FALSE;

    maze[y][x] = '+';

    if ( find_path(x, y - 1, c, t) == TRUE ) return TRUE;

    if ( find_path(x + 1, y, c, t) == TRUE ) return TRUE;

    if ( find_path(x - 1, y, c, t) == TRUE ) return TRUE;

    if ( find_path(x, y + 1, c, t) == TRUE ) return TRUE;

    maze[y][x] = oldMaze;   
    return FALSE;
}
4

1 に答える 1

0

まず、関数がTRUEを返すための基本条件が表示されません。再帰的に自分自身を呼び出すと、TRUEが返されるだけです。結果は常にFailedと出力されます（再帰には基本条件が必要だと思いました。成功を見つけることは上向きに伝播します。）

次に、ボックス内の値について説明していただけますか？0、1、2、3のように？3は迷路の終わりですか？...

于 2012-01-26T08:45:15.910 に答える