朝日新聞2004年7月17日パズルパーク(�U)解答

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

(0,0)右1(1,0)上2(1,2)右3(4,2)上4(4,6)左5(-1,6)下6(-1,0)左7(-8,0)上8(-8,8)左9(-17,8)下10(-17,-2)左11(-28,-2)下12(-28,-14)右13(-15,-14)上14(-15,0)右15(0,0)合計:120cm
(0,0)右1(1,0)上2(1,2)右3(4,2)上4(4,6)左5(-1,6)下6(-1,0)左7(-8,0)下8(-8,-8)左9(-17,-8)上10(-17,2)左11(-28,2)上12(-28,14)右13(-15,14)下14(-15,0)右15(0,0)合計:120cm
(0,0)右1(1,0)上2(1,2)右3(4,2)下4(4,-2)左5(-1,-2)上6(-1,4)左7(-8,4)上8(-8,12)左9(-17,12)下10(-17,2)左11(-28,2)上12(-28,14)右13(-15,14)下14(-15,0)右15(0,0)合計:120cm
(0,0)右1(1,0)上2(1,2)右3(4,2)下4(4,-2)左5(-1,-2)下6(-1,-8)左7(-8,-8)下8(-8,-16)左9(-17,-16)下10(-17,-26)左11(-28,-26)上12(-28,-14)右13(-15,-14)上14(-15,0)右15(0,0)合計:120cm

複数経路出力されるが，何れも120cmとなる。

ソースは以下の通り。

#include "puzutl.h"

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

int direcx( int dir, int dist) { switch(dir) { case 1: return dist; case 2: return -dist; default: return 0;}}
int direcy( int dir, int dist) { switch(dir) { case 3: return dist; case 4: return -dist; default: return 0;}}
void find( int ix, int iy, int dist)
{
  cstring direc[1+4] = {"★","右","左","上","下"};
  if( ix == 0 && iy == 0) {
    ps( "(0,0)", dist-1);
    int px = 0, py = 0;
    for( int i=1; i< dist; i++) {
      px += direcx(trace[i],i), py += direcy(trace[i],i);
      ps( "%s%d(%d,%d)", direc[trace[i]], i, px, py);
    }
    ps( "合計:%dcm\n", dist*(dist-1)/2);
    ynFind = YES;
    return;
  }
  if( dist >= maxdist) {
    return;
  }
  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);}
}

int main( int argc, cstring argv[]) 
{
  trace[1] = 1; trace[2] = 3; trace[3] = 1;
  do {
    maxdist++;
    find( 4, 2, 4);
  }while( !ynFind);
  return 0;
}