迷宮問題を再帰的に解く
1023 ワード
前に迷宮のストレージなどの準備を紹介しましたが、このブログでは再帰的な考え方で迷宮問題を解決することを紹介しています.再帰にはいくつかの要義がある:関数のどこで自分を呼び出して再帰するかを知っていて、言い換えれば再帰の条件は何で、それから再帰の出口は何ですか.
最初に現在位置が記録されているのが開始位置であり,ループ順で8個のブランチが歩けるか否かを判断し,できればこの次の位置の行と列を関数そのものに伝達し,再帰した.次の位置がだめであれば、次の方向にジャンプし、また、1つの位置の8つの方向に道がなければ、現在レイヤ関数を呼び出すと結果的に戻り、再帰の入り口に戻り、上のレイヤに戻り、次の方向にループを続けます.
再帰アルゴリズムを直接貼り付けます.
That's All;
最初に現在位置が記録されているのが開始位置であり,ループ順で8個のブランチが歩けるか否かを判断し,できればこの次の位置の行と列を関数そのものに伝達し,再帰した.次の位置がだめであれば、次の方向にジャンプし、また、1つの位置の8つの方向に道がなければ、現在レイヤ関数を呼び出すと結果的に戻り、再帰の入り口に戻り、上のレイヤに戻り、次の方向にループを続けます.
再帰アルゴリズムを直接貼り付けます.
int Maze::SeekPath(int current_row,int current_col)
{
int next_row,next_col;//
string next_direction;//
if(current_row == exit_row && current_col == exit_col)//
return 1;//
for(int i = 0;i < 8; i++)//8
{
next_row = current_row + Move[i].move_branch_row;
next_col = current_col + Move[i].move_branch_col;
next_direction = Move[i].direction;//
if(maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0)//
{
mark[next_row][next_col] = 1;// 1
if(SeekPath(next_row,next_col))
{
cout<
That's All;