朝日新聞2004年9月4日パズルパーク解答

プログラムの実行結果は以下の通り。長いので途中省略する。

 8[0,0], [1,0], [4,4]
 8[0,0], [1,0], [4,5]
 8[0,0], [1,0], [5,5]

ここに多数の出力あり,長いのでばっさりカット

 6[1,0], [6,4], [3,8]
 6[1,0], [7,4], [2,5]
 6[1,0], [7,4], [3,5]
 6[1,0], [7,4], [1,6]
 5[1,0], [7,4], [3,6]
 5[1,0], [7,4], [2,7]
 5[1,0], [7,4], [1,8]
 5[2,1], [7,4], [3,6]
 5[2,1], [7,4], [2,7]
 5[4,1], [2,5], [6,5]
0.296秒

一番左に出力されているのが距離。距離5(Km)が6件ある。これを図示すると以下の通り。パズルパークの解答欄て非常に小さいけどどうやって正答を表示するんだろう(2004.09.18新聞の解答欄にはプログラムが最後に出力したものが正答として掲載された,「他の置き方もあります」だって) 。

プログラムのソースは以下の通り。出力結果を目で見て重複除去するのは大変なので，重複除去を組み込んだら結構長くなってしまった。

#include "puzutl.h"

struct xy {
  int x, y;
}xy[81];

inline int distance( int i, int j) // 位置xy[i]と位置xy[j]間の距離を返す
{
  return abs(xy[i].x - xy[j].x) + abs(xy[i].y - xy[j].y);
}

inline int min3( int x, int y, int z) // 3つの数字のうち最小を返す
{
  return    min(min(x,y),z);
}

inline int distxy( int x, int y, int pos) // 位置(x,y)と位置xy[pos]間の距離を返す
{
  return abs(x - xy[pos].x) + abs(y - xy[pos].y);
}

void r90( int& x, int& y) // (x,y)を90度回転する,回転の中心は(4000,4000)
{
  x -= 4000;
  y -= 4000;
  int _x = -y, _y = x;
  x = _x + 4000;
  y = _y + 4000;
}

void turnx( int& x, int& y) // Y軸中心に回転
{
  x -= 4000; x = -x; x += 4000;
}

int cmpxy( const void* a, const void* b) // xy[]の小さい順にソートするための比較関数
{
  const struct xy* va = (const struct xy*)a;
  const struct xy* vb = (const struct xy*)b;
  if( va->y < vb->y) return -1;
  if( va->y > vb->y) return  1;
  if( va->x < vb->x) return -1;
  if( va->x > vb->x) return  1;
  return 0;
}

void sort(int&x1,int&y1,int&x2,int&y2,int&x3,int&y3) // 3点の位置をxy[]のINDEXが小さい順にソートする
{
  struct xy v[3] = { {x1, y1}, {x2, y2}, {x3, y3}};
  qsort(v,3,sizeof(v[0]),cmpxy);
  x1 = v[0].x; y1 = v[0].y; 
  x2 = v[1].x; y2 = v[1].y; 
  x3 = v[2].x; y3 = v[2].y; 
}
struct xyfind { // 発見した3点の位置を記録する
  int x1,y1,x2,y2,x3,y3;
}xyfind[2000]; // 1000だとエラーが出てしまうので一気に大きくした
int ifind = 0;
void regxyfind( int x1, int y1, int x2, int y2, int x3, int y3) // xyzinf[]に新しい3点の位置を登録する
{
  if( ifind >= sizeof(xyfind)/sizeof(xyfind[0])) { pe( "Overflow xyfind[%d]\n", sizeof(xyfind)/sizeof(xyfind[0])); exit(16);}
  xyfind[ifind].x1 = x1;  xyfind[ifind].y1 = y1;  xyfind[ifind].x2 = x2;  xyfind[ifind].y2 = y2;  xyfind[ifind].x3 = x3;  xyfind[ifind].y3 = y3;
  ifind++;
}
void find( int maxdist, int a, int b, int c)
{
  static int mdist = -1;
  if( maxdist != mdist) {
    // 新しい距離が見つかったので今まで登録して置いた位置は全て削除する
    ifind = 0;
    mdist = maxdist;
  }
  int x1, y1, x2, y2, x3, y3;
  x1 = xy[a].x; y1 = xy[a].y; x2 = xy[b].x; y2 = xy[b].y; x3 = xy[c].x; y3 = xy[c].y; sort(x1,y1,x2,y2,x3,y3);
  // 既に出現した位置と同じ位置が出現していたら見つかったことにはならない。
  for( int i=0; i< ifind; i++) {
    if( x1 == xyfind[i].x1 &&
        y1 == xyfind[i].y1 &&
        x2 == xyfind[i].x2 &&
        y2 == xyfind[i].y2 &&
        x3 == xyfind[i].x3 &&
        y3 == xyfind[i].y3) {
      return;
    }
  }
  // 既に出現した位置に同じ位置は無かったので出力する。出力するときは/1000をして判りやすくする。
  ps( "%2d[%d,%d], [%d,%d], [%d,%d]\n", maxdist/1000, xy[a].x/1000, xy[a].y/1000, xy[b].x/1000, xy[b].y/1000, xy[c].x/1000, xy[c].y/1000);
  // この3点の位置を登録する。回転，反転を加えて登録する。
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3); sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3);sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3);sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);

  x1 = xy[a].x; y1 = xy[a].y; x2 = xy[b].x; y2 = xy[b].y; x3 = xy[c].x; y3 = xy[c].y; turnx(x1,y1); turnx(x2,y2); turnx(x3,y3); sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3); sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3);sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
  r90(x1,y1); r90(x2,y2); r90(x3,y3);sort(x1,y1,x2,y2,x3,y3);
  regxyfind(x1,y1,x2,y2,x3,y3);
}

int main( int argc, cstring argv[])
{
  int           cnt = 0;
  ProcTime      pt;pt.start();
  for( int y=0; y< 9; y++) {
    for( int x=0; x< 9; x++) {
      xy[x + y*9].x = x*1000;
      xy[x + y*9].y = y*1000;
    }
  }
  int mindist = 8*1000;
  for( int a=0; a< 81; a++) {
    for( int b=a+1; b< 81; b++) {
      for( int c=b+1; c< 81; c++) {
        //a = 1; b = 42; c = 74;
        int maxdist = 0, dist;
        YesNo ng = NO;
        if( min3( distance(0,a), distance(0,b), distance(0,c)) > mindist || // まず四隅の点との距離を調べる,このチェックのあるなしで随分速度が変わる
            min3( distance(8,a), distance(8,b), distance(8,c)) > mindist ||
            min3( distance(64,a), distance(64,b), distance(64,c)) > mindist ||
            min3( distance(80,a), distance(80,b), distance(80,c)) > mindist) ng = YES;
        if( !ng) {
          for( int i=0; i< 81; i++) {
            if( i == a || i == b || i == c) continue;
            dist = min3( distance(i,a), distance(i,b), distance(i,c));
            if( dist > mindist) break;
            if( dist > maxdist) maxdist = dist;
          }
        }
        if( maxdist && maxdist <= mindist) {
          // 交差点の途中もこの距離で行けるか?
          // 全ての交差点の中点と3つの病院間の距離を計算し，maxdist以下ならOK。
          int ix1 = 500, iy1 = 0;
          int ix2 = 0, iy2 = 500;
          for( int ix=0; ix< 9; ix++) {
            iy1 = 0;
            ix2 = 0;
            for( int iy=0; iy< 9; iy++) {
              // (ix1,iy1)
              // (ix2,iy2)
              if( ix1 <= 8000 && iy1 <= 8000 && min3( distxy(ix1,iy1,a), distxy(ix1,iy1,b), distxy(ix1,iy1,c)) > maxdist) {
                ng = YES;
                break;
              }
              if( ix2 <= 8000 && iy2 <= 8000 && min3( distxy(ix2,iy2,a), distxy(ix2,iy2,b), distxy(ix2,iy2,c)) > maxdist) {
                ng = YES;
                break;
              }
              iy1 += 1000;
              ix2 += 1000;
            }
            if( ng) break;
            ix1 += 1000;
            iy2 += 1000;
          }
          if( !ng) {
            // 見つかった3地点が既に登録されていないか調べる
            find(maxdist,a,b,c);
            mindist = maxdist;
          }
        }
      }
    }
  }
  pt.end();
  ps( "%g秒\n", pt.sec());
  return    0;
}