/*
2003/08 ひと筆長旅
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ 49個の点が7×7の正方格子状に並んでいる。Fig.3のよう│
 │に,Aから矢印の方向に入り,ひと筆書きで点をつないでいって│
 │Bから矢印の方向に出たい。ただし,途中直角に曲がるのは13│
 │回とし,それ以外は直進しなければならない。同じ点を通ること│
 │は可能だが,同じパス(点と点を結ぶ線)は通れない。点と点を結│
 │ぶ1つのパスの長さを1cmとすると,最長のルートは何cmとなる│
 │だろうか。また,その最長のルートで,もっともたくさんの点を│
 │通るルートを1つ示してほしい。              │
 │ 例は,52cmのルートで46個の点を通っている。もちろん,│
 │これは最長のルートではない。               │
 │                             │
 │Fig.3 ひと筆書きの例                  │
 │     A                       │
 │     ↓                       │
 │ ●━●━●━●━●━●━●               │
 │ ┃   ┃       ┃               │
 │ ● ●━●━● ● ● ●               │
 │ ┃ ┃ ┃ ┃     ┃               │
 │ ● ●━●━●━●━●━●→B             │
 │ ┃   ┃ ┃     ┃               │
 │ ● ●━●━●━●━● ●               │
 │ ┃ ┃ ┃ ┃   ┃ ┃               │
 │ ● ● ● ● ● ● ●               │
 │ ┃ ┃ ┃ ┃   ┃ ┃               │
 │ ● ● ● ●━●━● ●               │
 │ ┃ ┃ ┃       ┃               │
 │ ●━● ●━●━●━●━●               │
 │                             │
 └─────────────────────────────┘
 ┌────────┐
 │解答:     │
 │┏━╋━━━┓ │
 │┃┏╋━━┓┃ │
 │┗╋╋━━╋╋ │
 │┏╋╋━━╋┛ │
 │┃┗╋━━╋┓ │
 │┃・┗━━┛┃ │
 │┗━━━━━┛ │
 │最長 58 cm.   │
 │点の数 48.   │
 └────────┘
 ┌──────────────┬────┬───────┐
 │コンパイラ         │実行時間│ファイルサイズ│
 ├──────────────┼────┼───────┤
 │Microsoft Visual C++ 6.0  │0.3828秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.4640秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.5671秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.6703秒│ 109805 byte │
 │gcc-2.953(cygwin)      │0.6125秒│ 20829 byte │
 │LSI C-86 Ver 3.30 試食版  │1.0490秒│ 14064 byte │
 │Turbo C Ver 1.5(small model)│1.2350秒│ 11740 byte │
 ├──────────────┼────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP   │
 └──────────────┴────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 盤を表すのに13×13のchar型2次元配列Map[][]を使いました。│
 │添え字が共に偶数の要素は点を表し、添え字のどちらか一方が偶│
 │数で残りが奇数の要素はパスを表します。添え字が共に奇数の要│
 │素は使いません。点の要素はルートがその点の上を何回通過した│
 │かを表し、パスの要素はルートに含まれていれば1、そうでなけ │
 │れば0です。                        │
 │ 探索は深さが14の再帰呼び出しをする関数で行います。引数 │
 │restは、あと何回曲がれるかを表します。最初が13で、曲がるた│
 │びに再帰呼び出しをして減らしてゆき、13回曲がると0になりま │
 │す。                           │
 │ 関数の先頭のforループで、直線を伸ばせるまで伸ばしてゆき │
 │ます。直線が盤の範囲を超えたり、既に通ったパスに到達したり│
 │すると、ループは終了します。このときMap[][]と長さを設定し │
 │ます。                          │
 │ 2つ目のforループでは、直線を縮ませながら処理をしてゆき │
 │ます。                          │
 │ そのループの先頭で、再帰呼び出しをして、右に曲がったり、│
 │左に曲がったりします。ただし、最大の長さと同じか長くなる見│
 │込みが無かったり、入口の場合を除いて直線の長さが0だったり │
 │すれば、曲がりません。                  │
 │ ループの中ほどでは、restが0で方向と座標が出口に到達して │
 │いて、ルートの長さが最大の長さと同じか長ければ、解としてル│
 │ートをログに記録します。ただし、通過した点の数を数えて、点│
 │の数が最大の数より小さければ記録しません。ルートの長さや点│
 │の数を更新したら、ログをリセットします。         │
 │ ループの終わりのほうでは、直線を縮ませ、Map[][]と長さを │
 │元に戻します。                      │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 最初は直線を伸ばしながら再帰呼び出しをしていたのですが、│
 │縮めながらにしたところ計算時間が半分以下に短縮されました。│
 │ パラメータをいろいろと変えながら試してみて楽しみました。│
 └─────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum { DOWN, LEFT, UP, RIGHT };        /* 方向を表す */
enum { X=7, Y=7, TURN=13 };            /* 盤の大きさと曲がる回数 */
enum { AX=2,   AY=0, ADIR=DOWN  };     /* 入口Aの座標と方向 */
enum { BX=X-1, BY=2, BDIR=RIGHT };     /* 出口Bの座標と方向 */
enum { SCREEN=80 };                    /* 画面の幅 */
enum { LOG=50700U/((X*2-1)*(Y*2-1)) }; /* ログの大きさ */
const int DX[]={0,-1, 0,1};  /* 方向に対応する単位ベクトル */
const int DY[]={1, 0,-1,0};

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Map[Y*2-1][X*2-1];      /* 盤(点とパスを混ぜて表している) */
int  MaxLen,MaxDot;          /* 現れた最大の長さと最大の個数 */
int  SizeOfLog,MaxLog;       /* 溜まった解の数とその最大値 */
char Log[LOG][Y*2-1][X*2-1]; /* ログ */

/*┌──────────────────────┐
 │盤を書き出す。引数を0にするとフラッシュする│
 └──────────────────────┘*/
void Print(char map[Y*2-1][X*2-1])
{
    int x,y,k; static char buf[Y][SCREEN]; static int col;

    if (map) {
        for (y=0;y<Y*2;y+=2) {
            if (col) strcat(buf[y/2],"  ");
            for (x=0;x<X*2;x+=2) {
                k=0;
                if (y==AY*2&&x==AX*2)     k|=1<<(ADIR^2); /* 入口 */
                if (y==BY*2&&x==BX*2)     k|=1<<BDIR;     /* 出口 */
                if (y<Y*2-2&&map[y+1][x]) k|=1<<DOWN;
                if (x>0    &&map[y][x-1]) k|=1<<LEFT;
                if (y>0    &&map[y-1][x]) k|=1<<UP;
                if (x<X*2-2&&map[y][x+1]) k|=1<<RIGHT;
                sprintf(buf[y/2]+strlen(buf[y/2]),"%.2s",
                    "・┃━┓┃┃┛┫━┏━┳┗┣┻╋"+k*2);
            }
        }
        col++;
    }
    if ((map==0&&col)||col>=SCREEN/((X+1)*2)) {
        for (y=0;y<Y;y++) { printf("%s\n",buf[y]); buf[y][0]=0; }
        printf("\n"); col=0;
    }
}

/*┌───────────────────┐
 │再帰呼び出しをしながら、パズルを解く │
 │rest:曲がれる回数. dir,x,y:方向と座標.│
 └───────────────────┘*/
void Solve(int rest,int dir,int x,int y)
{
    int n,dx=DX[dir],dy=DY[dir]; static int len;

    /* 伸ばせるまでのばす。n は伸ばした回数 */
    for (n=0;;n++) {
        x+=dx; y+=dy;
        if (x<0||y<0||x>=X*2-1||y>=Y*2-1||Map[y][x]) break;
        Map[y][x]=1; Map[y+=dy][x+=dx]++; len++;
    }

    /* 縮ませながら、再帰呼び出ししたり、検査したりする */
    for (;;n--) {

        x-=dx; y-=dy;

        /* MaxLenと同じか長くなる可能性があるなら曲がる */
        /* 入口を除いて直線距離が0なら曲がらない */
        if (len+rest*((X>Y?X:Y)-1)>=MaxLen&&rest&&(n||rest==TURN)) {
            Solve(rest-1,(dir+1)&3,x,y);
            Solve(rest-1,(dir-1)&3,x,y);
        }

        /* 決められた回数で出口に到達した時の処理 */
        if (rest==0&&dir==BDIR&&x==BX*2&&y==BY*2&&len>=MaxLen) {

            /* 通過した点の数を数える */
            int i,j,dot=X*Y;
            for (i=0;i<Y*2;i+=2) for (j=0;j<X*2;j+=2)
             if (Map[i][j]==0) dot--;

            if (len>MaxLen) { MaxLen=len; MaxDot=0; SizeOfLog=0; }
            if (dot>MaxDot) { MaxDot=dot; SizeOfLog=0; }
            if (dot==MaxDot) {
                if (SizeOfLog>=LOG)
                { printf("ログが小さい\n"); exit(1); }
                memcpy(Log[SizeOfLog++],Map,sizeof Map);
                if (SizeOfLog>MaxLog) MaxLog=SizeOfLog;
            }
        }

        if (n==0) break;

        /* 直線を縮める */
        Map[y][x]--; Map[y-=dy][x-=dx]=0; len--;
    }
}

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────┐
 │メイン・ルーチン│
 └────────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) {
        Map[AY*2][AX*2]=1; MaxLen=MaxDot=SizeOfLog=MaxLog=0;
        Solve(TURN,ADIR,AX*2,AY*2);
    }
    for (i=0;i<SizeOfLog;i++) Print(Log[i]);
    Print(0); printf("長さ%dcm  点の数%d  ",MaxLen,MaxDot);
    printf("解の数%d  ログの使用状況%d/%d  ",SizeOfLog,MaxLog,LOG);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}