朝日新聞2004年12月25日のパズルパーク問題その2

問題

以下の▽を出発し全てのT字路を経由し戻ってくる一筆書きの経路のうち最長となるものを求める。交差点間の距離は短い順に100m，200m，300mとする。

解答への道(ヒント)

迷路問題と見なすことが出来る。迷路問題の定石として交差点(この問題ではT字路)に番号を振る。

交差点間の接続を変数で定義する。定義するのは小さい番号から大きい番号の一方向だけでよい。プログラムの中で逆方向の経路は自動で生成する。

P[1][2] = 1;
P[1][11] = 1;
P[2][3] = 1;
P[2][6] = 1;
P[3][4] = 1;
P[3][7] = 1;
P[4][5] = 1;
P[4][10] = 1;
P[5][16] = 1;
P[6][7] = 1;
………

findGoal()でGoalの判定の前に一度到達した点かどうかの判断を入れているので，その順序を逆にする。Goal地点に到達したとき，全ての点を通過したかの判断を追加する。

void findGoal( int level, int p)
{
  visit[level] = p;
  if( p==g && level == S) {
    printf( "FindGoal ");
    for( int i=0; i<= level; i++) {
      printf( "%d ", visit[i]);
    }
    printf( "\n");
    return;
  }
  if( once[p]) return; // 一度通った地点
  once[p] = 1;
  for( int next=1; next<= S; next++) { // pから到達可能な全ての地点を調べる
    if( !P[p][next]) {
      continue; // 到達出来ない地点は無視する
    }
    findGoal( level+1, next);
  }
  once[p] = 0;
}

結果は複数件出力される。しかし，これだと距離が判らないので，距離も判るように点間の接続を示す変数に接続情報だけでなく，距離情報を入れる。

P[1][2] = 1; // 100m
P[1][11] = 2; // 200m
P[2][3] = 1;
P[2][6] = 1;
P[3][4] = 3; // 300m
P[3][7] = 1;
P[4][5] = 1;
P[4][10] = 1;
P[5][16] = 2;
P[6][7] = 1;
………

こうしておいて，findGoal()のGoal判定部分を以下のように変更する。

  if( p==g && level == S) {
    int dist = 0;
    printf( "FindGoal ");
    for( int i=0; i<= level; i++) {
      printf( "%d ", visit[i]);
      if( i>0) dist += P[visit[i]][visit[i-1]];
    }
    printf( ": 距離 %dm\n", dist*100);
    return;
  }

結果は10件出力されるが，一番距離の大きいのは2件。但し，方向が逆なだけなので実質1件。

解速度

即