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

プログラムの実行結果は以下の通り。

FindGoal 1 2 3 4 5 16 27 32 31 25 26 22 15 10 9 21 20 24 23 30 29 28 17 18 19 13 14 8 7 6 12 11 1 : 距離 4000m
FindGoal 1 2 3 4 5 16 27 32 31 30 23 24 25 26 22 15 10 9 21 20 14 8 7 6 12 13 19 18 29 28 17 11 1 : 距離 4200m
FindGoal 1 2 3 7 6 12 13 14 8 9 10 4 5 16 15 22 21 20 24 25 26 27 32 31 30 23 19 18 29 28 17 11 1 : 距離 3800m
FindGoal 1 2 3 7 6 12 13 14 8 9 21 20 24 25 26 22 15 10 4 5 16 27 32 31 30 23 19 18 29 28 17 11 1 : 距離 4000m
FindGoal 1 2 6 7 3 4 5 16 15 10 9 8 14 20 21 22 26 27 32 31 25 24 23 30 29 28 17 18 19 13 12 11 1 : 距離 3800m
FindGoal 1 11 12 6 7 8 14 13 19 18 17 28 29 30 23 24 20 21 9 10 15 22 26 25 31 32 27 16 5 4 3 2 1 : 距離 4000m
FindGoal 1 11 12 13 19 18 17 28 29 30 23 24 25 31 32 27 26 22 21 20 14 8 9 10 15 16 5 4 3 7 6 2 1 : 距離 3800m
FindGoal 1 11 17 28 29 18 19 13 12 6 7 8 14 20 21 9 10 15 22 26 25 24 23 30 31 32 27 16 5 4 3 2 1 : 距離 4200m
FindGoal 1 11 17 28 29 18 19 23 30 31 32 27 16 5 4 10 15 22 26 25 24 20 21 9 8 14 13 12 6 7 3 2 1 : 距離 4000m
FindGoal 1 11 17 28 29 18 19 23 30 31 32 27 26 25 24 20 21 22 15 16 5 4 10 9 8 14 13 12 6 7 3 2 1 : 距離 3800m

4200mが一番大きい。4200mは2件出力されているが，左右対称なので実質1件。

解答の道筋を図示すると以下の通り。長い経路は全て通っていることが判る。

プログラムのソースは以下の通り。

#include 
#include 

int s=1;
int g=1;
#define S 32
int P[S+1][S+1];
int once[S+1];
int visit[S+1];

void findGoal( int level, int p)
{
  visit[level] = p;
  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;
  }
  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;
}

int main( int argc, const char* argv[])
{
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;
P[6][12] = 1;
P[7][8] = 1;
P[8][9] = 1;
P[8][14] = 1;
P[9][10] = 1;
P[9][21] = 2;
P[10][15] = 1;
P[11][12] = 1;
P[11][17] = 1;
P[12][13] = 1;
P[13][14] = 1;
P[13][19] = 1;
P[14][20] = 1;
P[15][16] = 1;
P[15][22] = 1;
P[16][27] = 2;
P[17][18] = 1;
P[17][28] = 2;
P[18][19] = 1;
P[18][29] = 2;
P[19][23] = 1;
P[20][21] = 1;
P[20][24] = 1;
P[21][22] = 1;
P[22][26] = 1;
P[23][24] = 1;
P[23][30] = 1;
P[24][25] = 1;
P[25][26] = 1;
P[25][31] = 1;
P[26][27] = 1;
P[27][32] = 1;
P[28][29] = 1;
P[29][30] = 1;
P[30][31] = 2;
P[31][32] = 2;
  for( int i=0; i<= S; i++) for( int j=0; j<= S; j++) if( P[i][j]) P[j][i] = P[i][j];
  findGoal( 0, s);
  return 0;
}