再帰的な迷路ソルバーを最適化する方法

Question

私は、迷路から出る可能性のあるすべての経路を見つけるために次の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; 
} 

Answer 1

私はTRUE返すように関数のいずれかの基本条件が表示されないまず第一に、それだけで再帰的に魔女自体を呼び出すにはTRUEを返し、それが結果はオールウェイズ（私は再帰が持っていたと思った失敗に印刷されますでしょうと言うことです）成功すると上向きに伝播する基本条件を持つようにします。）

第2に、ボックスの値を説明してください。 0,1,2,3のように？ 3は迷路の終わりですか、それとも...？