朝日新聞2004年7月17日のパズルパーク問題(�U)

問題

座標位置(0,0)から出発し，右へ1cm，上に2cm，右へ3cm移動する。

以降1cmずつ距離を増やし，方向は必ず90度ずつ変更する。(0,0)に戻って来るには最短で合計何cmになるか。

解答への道(ヒント)

幅優先の探索。深さ優先で一定数で打ち切っても良い。

問題は距離だけを求めるようになっているが，経路も出力したいので，経路も記録する。

int trace[100]; // 方向を記録する(1:右,2:左,3:上,4:下)

trace[ ]のINDEXは距離を使う。

探索の肝となる部分は以下のようにする。

void find( int ix, int iy, int dist)
{
  if( ix == 0 && iy == 0) {
    (0,0)に戻ってきた，経路発見
  }
  if( trace[dist-1] == 3 || trace[dist-1] == 4) { trace[dist] = 1; find( ix + dist, iy, dist+1);} // 直角に曲がる
  if( trace[dist-1] == 3 || trace[dist-1] == 4) { trace[dist] = 2; find( ix - dist, iy, dist+1);}
  if( trace[dist-1] == 1 || trace[dist-1] == 2) { trace[dist] = 3; find( ix, iy + dist, dist+1);}
  if( trace[dist-1] == 1 || trace[dist-1] == 2) { trace[dist] = 4; find( ix, iy - dist, dist+1);}
}

(ix,iy)は直前の位置，distは次に進む距離を示す。

経路は4件出力される。

解速度

即