ブロック
2010.01.21 20:01 パソコン甲子園 2009
パソコン甲子園2009 問題03 ブロック
2次元グリッド(配列)上に迷路を作り、スタートのマスからゴールのマスまでの道があるかどうかを判定する問題です。各マスには色がつけられ、色が同じマス間を上下左右の方向に移動することができます。
深さ優先探索または幅優先探索によって解くことができます。以下に示す解答プログラムでは深さ優先探索を実装しています。深さ優先探索は、一度訪問したマスを二度訪問しないように注意しながら、再帰的に隣接するマスを訪問していくアルゴリズムです。プログラムの関数dfsに示すように、グリッドにおける探索の問題では、現在地からのx方向及びy方向への移動距離を示すdx[4]、dy[4]を宣言しておくと、グリッドのマス間の移動の記述を簡潔に記述することができます。
2次元グリッド(配列)上に迷路を作り、スタートのマスからゴールのマスまでの道があるかどうかを判定する問題です。各マスには色がつけられ、色が同じマス間を上下左右の方向に移動することができます。
深さ優先探索または幅優先探索によって解くことができます。以下に示す解答プログラムでは深さ優先探索を実装しています。深さ優先探索は、一度訪問したマスを二度訪問しないように注意しながら、再帰的に隣接するマスを訪問していくアルゴリズムです。プログラムの関数dfsに示すように、グリッドにおける探索の問題では、現在地からのx方向及びy方向への移動距離を示すdx[4]、dy[4]を宣言しておくと、グリッドのマス間の移動の記述を簡潔に記述することができます。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |