/*
2002/01 見た目は月並みですが
coded by Isaku WADA
 ┌────────────────────────────┐
 │ 英語の1月から12月までの12単語を,Fig.1のように正│
 │方形のマス目に配置する。配置する際の条件は以下の4つ。 │
 │ (1)1マスに1文字を書く              │
 │ (2)各単語は左から右,または上から下に向かって読める│
 │    ように配置する。ナナメは考えない        │
 │ (3)各単語は,必ず1つ以上のほかの単語とつながってい│
 │    る。ここでいう「つながっている」とは,2つの単語│
 │    が同じ文字の部分でオーバーラップして配置されてい│
 │    る状態のことで,単に隣接して配置しただけではつな│
 │    がったことにならない              │
 │ (4)全体が1つのつながりでできている。一部が環になっ│
 │    ていてもかまわない               │
 │ Fig.1は上記の条件を満たしており,この外接長方形の面積│
 │は120(=8×15)となっている。上記条件を満たしつつ│
 │もっとじょうずに12単語を配置して,外接長方形の面積をで│
 │きるだけ小さくしたい。最小面積はいくつか。そのときの配置│
 │は1つ示せばよいことにする。なお,英語名はFig.1に登場し│
 │ている単語を使い,省略形は不可である。         │
 │                            │
 │Fig.1 パズルの解の例                 │
 │                            │
 │    ■■■■■F■■■■■D■■■         │
 │    ■■■■SEPTEMBER■■         │
 │    ■MAY■B■■■■■C■■■         │
 │    JANUARY■■■■E■■■         │
 │    UR■■PU■NOVEMBER         │
 │    NC■■RAUGUSTB■■■         │
 │    EH■■IROCTOBER■■         │
 │    ■■JULY■■■■■R■■■         │
 │                            │
 └────────────────────────────┘
 ┌────────────┐
 │解答:10×8=80     │
 │            │
 │ ■M■■M■■■NF │
 │ JANUARY■OE │
 │ UYAPRIL■VB │
 │ L■DECEMBER │
 │ YJ■■H■■■MU │
 │ AUGUST■■BA │
 │ ■N■OCTOBER │
 │ SEPTEMBERY │
 │            │
 └────────────┘
 ┌──────────────┬────┬───────┐
 │コンパイラ         │実行時間│ファイルサイズ│
 ├──────────────┼────┼───────┤
 │Microsoft Visual C++ 6.0  │ 6.12 秒│ 36864 byte │
 │Borland C++ 5.5 for Win32  │ 7.01 秒│ 54784 byte │
 │gcc-2.953(djgpp)      │ 6.08 秒│ 110571 byte │
 │gcc-2.953(cygwin)      │ 7.11 秒│ 374182 byte │
 │LSI C-86 Ver 3.30 試食版  │11.35 秒│ 14528 byte │
 │Turbo C Ver 1.5(small model)│11.45 秒│ 11960 byte │
 ├──────────────┼────┴───────┤
 │ CPU:Pentium!!! 550 MHz │  OS:Windows 98   │
 └──────────────┴────────────┘

 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │英語の月名に限れば、先頭文字集合と終了文字集合に共通の要素が│
 │なく、一直線上にオーバーラップすることがありません。従って、│
 │マス目の取り得る状態として、空(NONE)、縦方向の単語上(TATE)、│
 │横方向の単語上(YOKO)、縦横のオーバーラップ上(BOTH)、の4つの│
 │場合だけを考えればよいことになります。           │
 │                              │
 │プログラムは高速化のために、英文字に対して、それが出現する月│
 │とその位置を記録する早見表を持ちます。例えば'C'ならば内容と│
 │して、月が2(MARCH)で位置が3、月が9(OCTOBER)で│
 │位置が1、月が11(DECEMBER)で位置がの2のような、長│
 │さ3のリストを持ちます。                  │
 │                              │
 │探索の前処理として、JANUARYを大きめな盤の中央に並べ、│
 │その状態をYOKOに設定し、各文字をキューに登録します。    │
 │                              │
 │探索はキューから文字を取り出し、その状態がBOTHでなければ、オ│
 │ーバーラップする可能性のある単語を早見表から探し、再帰呼び出│
 │しをしながら盤に次々と置いてゆきます。この時、既に別の文字が│
 │置いてある場合は無視します。また、置いた文字をキューにも登録│
 │してゆきます。キューから取り出した文字の状態がTATEならば新し│
 │い単語は横に並べ、新しい文字の状態はYOKOにします。YOKOならば│
 │新しい単語は縦に並べ、新しい文字の状態はTATEにします。新しい│
 │文字の下が既にTATEかYOKOならばその文字の下をBOTHにします。 │
 │                              │
 │探索の時に、全ての単語を置くことができたら、その時の盤を表示│
 │します。枝刈りとして、外接長方形の面積が必要以上に大きくなっ│
 │たら、それ以上は調べません。                │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │面積が80まで小さくなったのには驚きました。空白が18個しか│
 │ありません。                        │
 └──────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define LIMIT 120 /* 外接長方形の面積の制限の初期値 */
#define WIDTH 100 /* 作業用の正方形の盤の一辺の長さ */
#define TOTAL 100 /* 1月を除く単語の文字数以上の値 */
enum { NONE,TATE,YOKO,BOTH }; /* Status[][] のとる値 */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char*Name[12]= /* 単語 */
{ "JANUARY","FEBRUARY","MARCH","APRIL","MAY","JUNE","JULY",
  "AUGUST","SEPTEMBER","OCTOBER","NOVEMBER","DECEMBER" };
int  Size[12];     /* 単語の長さ */
char Flag[12]={1}; /* 単語が既に現れたかどうかのフラグ */
char Map[WIDTH][WIDTH];    /* 正方形の盤(文字が記録される) */
char Status[WIDTH][WIDTH]; /* 正方形の盤(状態が記録される) */
int  Limit;          /* 現在まで出現した最も小さい解の面積 */
int AlphaTbl[26];  /* 早見表の各文字ごとのリストの先頭 */
int Mon[TOTAL+1];  /* 同じ文字を含む月のリスト         */
int Pos[TOTAL+1];  /* 同じ文字の位置のリスト           */
int Next[TOTAL+1]; /* 同じ文字のリストの次の要素       */
int QueX[TOTAL],QueY[TOTAL]; /* キュー       */
int QueTail;                 /* キューの長さ */

/*┌────────────────┐
 │現在の Map を全角文字で書き出す │
 └────────────────┘*/
void Print(int left,int right,int top,int bottom)
{
    static char Alpha[]=
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int i,j,x=right-left+1,y=bottom-top+1;

    Limit=x*y;
    printf("%d×%d=%d\n",x,y,Limit);
    for (i=top;i<=bottom;i++) {
        for (j=left;j<=right;j++)
         if (Map[i][j]) printf("%.2s",Alpha+(Map[i][j]-'A')*2);
         else printf("■");
        printf("\n");
    }
    printf("\n");
}

/*┌──────────────────┐
 │再帰呼び出しをしながら、解を探す関数│
 └──────────────────┘*/
void SubFunc(int QueHead,int left,int right,int top,int bottom)
{
    static int level=1; int ptr;

    /* 範囲が必要以上に大きくなったら探索を止める */
    if ((right-left+1)*(bottom-top+1)>=Limit) return;

    /* 単語を全部置けたら表示する */
    if (level>=12) { Print(left,right,top,bottom); return; }

    /* 過去に置いた文字について繰り返す */
    for (ptr=QueHead;ptr<QueTail;ptr++) {
        int y=QueY[ptr],x=QueX[ptr],dir=Status[y][x],p;
        if (dir==BOTH) continue; /* 既に交差点ならば無視する */

        /* 同じ文字のリストについて繰り返す */
        for (p=AlphaTbl[Map[y][x]-'A'];p;p=Next[p])
         if (Flag[Mon[p]]==0) { /* 出現していない月に限定する */
             int i,u,v,Min,Max,mon=Mon[p],size=Size[mon],pos=Pos[p];

             /* 新しい範囲を求める */
             if (dir==TATE) {
                 if (x-pos<left) Min=x-pos; else Min=left;
                 if (x+size-pos-1>right) Max=x+size-pos-1;
                 else Max=right;
             } else {
                 if (y-pos<top) Min=y-pos; else Min=top;
                 if (y+size-pos-1>bottom) Max=y+size-pos-1;
                 else Max=bottom;
             }

             /* 新しい範囲が盤を超えようとしたらエラーにする */
             if (Min<0||Max>=WIDTH)
             { printf("ERROR: WIDTH is too small\n"); exit(1); }

             /* 違った文字が既にある場合は無視する */
             if (dir==TATE) { u=x-pos; v=y; } else { u=x; v=y-pos; }
             for (i=0;i<size;i++) {
                 if (Map[v][u]&&Name[mon][i]!=Map[v][u]) break;
                 if (dir==TATE) u++; else v++;
             }
             if (i<size) continue; /* ※前の版では break だった */

             /* 文字を Map,Status に置き、キューにも追加する */
             if (dir==TATE) { u=x-pos; v=y; } else { u=x; v=y-pos; }
             for (i=0;i<size;i++) {
                 Map[v][u]=Name[mon][i];
                 if (Status[v][u]==NONE) {
                     Status[v][u]=(char)(dir^BOTH);
                     QueX[QueTail]=u; QueY[QueTail]=v; QueTail++;
                 }else Status[v][u]=BOTH;
                 if (dir==TATE) u++; else v++;
             }

             /* 再帰呼び出し */
             Flag[mon]=1; level++;
             if (dir==TATE) SubFunc(ptr+1,Min,Max,top,bottom);
             else           SubFunc(ptr+1,left,right,Min,Max);
             level--; Flag[mon]=0;

             /* Map,Status,キューを元に戻す */
             if (dir==TATE) { u=x-pos; v=y; } else { u=x; v=y-pos; }
             for (i=0;i<size;i++) {
                 if (Status[v][u]==BOTH) Status[v][u]=(char)dir;
                 else { Status[v][u]=NONE; Map[v][u]=0; QueTail--; }
                 if (dir==TATE) u++; else v++;
             }
         } 
    }
}  

/*┌──────┐
 │パズルを解く│
 └──────┘*/
void Solve(void)
{
    int i,j,c,k;

    Limit=LIMIT;

    /* 単語の長さを求める */
    for (i=0;i<12;i++) Size[i]=strlen(Name[i]);

    /* 同じ文字のリスト(早見表)を作成する */
    memset(AlphaTbl,0,sizeof AlphaTbl);
    for (k=i=1;i<12;i++) for (j=0;j<Size[i];j++) {
        if (k>TOTAL)
        { printf("ERROR: TOTAL is too small\n"); exit(1); }
        c=Name[i][j]-'A'; Next[k]=AlphaTbl[c]; Mon[k]=i;
        Pos[k]=j; AlphaTbl[c]=k; k++;
    }

    /* 1月のデータを登録する */
    memcpy(&Map[WIDTH/2][WIDTH/2-4],Name[0],Size[0]);
    memset(&Status[WIDTH/2][WIDTH/2-4],YOKO,Size[0]);
    for (i=0;i<Size[0];i++)
    { QueX[i]=WIDTH/2-4+i; QueY[i]=WIDTH/2; }
    QueTail=Size[0];

    /* 探索の開始 */
    SubFunc(0,WIDTH/2-4,WIDTH/2-4+Size[0]-1,WIDTH/2,WIDTH/2);
}

/*┌────────────────────┐
 │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++) Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}