#include "puzutl.h"

// 問題文は3部構成で以下の並び順になる。
// ・マトリックスの定義。
// ・単語一覧
// ・解答欄の位置
int rows = 0, columns = 0;
int prevColumns = 0;

#define SOLVES  100
#define M 100
#define N 100
int mat[M][N];                  // 0:文字無し，1:文字あり，2:文字解答
struct st_solve {
  int row;                      // 0オリジンの位置,入力は1オリジンなので-1してから設定する。
  int col;
} solve[SOLVES];
int numSolve;

#define WORDLISTS   1000
struct st_wordList {
  int row;
  int col;
  string s;
  int direction;                // 1:横,2:縦
  int len;                      // 文字数
} wordList[WORDLISTS];
int numWordList;

// 単語一覧
struct st_wordIndex {
  int           pos;            // 単語位置 index to wordDic[]
  int           num;            // 単語数
} wordIndex[100];
int numWordIndex;
struct st_wordDic {
  string s;                     // 単語
  YesNo used;                   // この単語を矩形に当てはめたか？
  int len;                      // 単語の文字数(バイト長でなく文字数)
} wordDic[1000];
int numWordDic;                 // 有効な単語数

void readProblemMatrix( cstring p)
{
  int n;
  // 文字部分，影部分の順に指定する。
  int type = 1;
  columns = 0;
  while( *p) {
    n = eval(p);
    while( n--> 0) {
      if( type & 1) {
        mat[rows][columns] = 1;
      }
      else {
        mat[rows][columns] = 0;
      }
      columns++;
    }
    type++;
  }
  if( prevColumns != 0 && columns != prevColumns) Option::abort( "カラム数(%d)が前の行のカラム数と一致しない(%d)@%d行", columns, prevColumns,rows+1);
  prevColumns = columns;
  rows++;
}

string conv_to_capital_katakana( cstring s)
{
  char buf[2048];
  strcpy( buf, s);
  conv_hirakana_to_katakana(buf);
  to_capital_katakana(buf);
  return buf;
}

void readProblemWord( cstring s)
{
  int L = strlen(s);
  if( !*s) {
    return;
  }
  if( L & 1) {
    pe( "文字列(%s)が日本語でない可能性があります\n");
    return;
  }
  L /= 2;
  if( L < 2) {
    pe( "２文字以下の単語(%s)を扱うことができません\n", s);
    return;
  }
  if( numWordDic == 0 || wordDic[numWordDic-1].len != L) {
    // 新しい長さの単語が出現した。
    if( numWordDic != 0 && L < wordDic[numWordDic-1].len) {
      pe( "単語は短い順に指定しなければなりません,(%s)(%s)\n", wordDic[numWordDic-1].s.c_str(), s);
      return;
    }
    wordIndex[L].pos = numWordDic;
    wordIndex[L].num = 0;
    if( L > numWordIndex) {
      numWordIndex = L;
    }
  }
  wordIndex[L].num++;
  wordDic[numWordDic].s = conv_to_capital_katakana(s);
  wordDic[numWordDic].used = NO;
  wordDic[numWordDic].len = L;
  numWordDic++;
}

void readProblemPosition( cstring s)
{
  // 以下の形式の文字列が続く。
  // 1.9
  int row, col;
  cstring p = s;
  if( !*s) return;
  row = eval(s)-1;
  col = eval(s)-1;
  solve[numSolve].row = row;
  solve[numSolve].col = col;
  if( mat[row][col] == 1) {
    mat[row][col] = 2;
    numSolve++;
  }
  else if( mat[row][col] == 0) {
    pe( "解答欄の位置(行:%d,列:%d)に文字がありません\n", row+1, col+1);
  }
  else {
    pe( "解答欄の位置(行:%d,列:%d)は既に定義されています\n", row+1, col+1);
  }
}

void readProblem( cstring fn)
{
  TextFile      tf(fn);
  cstring s;
  int type = 0;
  while( s=tf.gets()) {
    if( *s == '#') {
      type++;
      continue;
    }
    switch(type) {
    case 0:
      readProblemMatrix(s);
      break;
    case 1:
      readProblemWord(s);
      break;
    case 2:
      readProblemPosition(s);
      break;
    default:
      Option::abort( "#が多すぎる");
    }
  }
}

void dumpMat()
{
  // 読み込んだ問題を表示する。
  int row, column;
  ps( "MAT[%d][%d]\n", rows, columns);
  for( row=0; row < rows; row++) {
    for( column=0; column < columns; column++) {
      if( mat[row][column] == 0) ps( "■");
      else if( mat[row][column] == 1) ps( "□", mat[row][column]);
      else ps( "※", mat[row][column]);
    }
    ps( "\n");
  }
  int i, j, numWord = 0;
  for( i=2; i<= numWordIndex; i++) {
    for( j=0; j< wordIndex[i].num; j++) {
      int pos = wordIndex[i].pos + j;
      ps( "%2d : %s\n", i, wordDic[pos].s.c_str());
      numWord++;
    }
  }
  ps( "有効単語数 : %d\n", numWord);
  for( i=0; i< numWordList; i++) {
    if( wordList[i].direction == 1) 
      ps( "%2d : %s[%2d][%2d] : %2d \n", i+1, (wordList[i].direction==1)?"横":"縦", wordList[i].row, wordList[i].col, wordList[i].len);
  }
  for( i=0; i< numWordList; i++) {
    if( wordList[i].direction == 2) 
      ps( "%2d : %s[%2d][%2d] : %2d \n", i+1, (wordList[i].direction==1)?"横":"縦", wordList[i].row, wordList[i].col, wordList[i].len);
  }
  if( numWord != numWordList) {
    pe( "単語数が合わない(矩形内の単語数:%d,入力した単語数:%d)\n", numWordList, numWord);
  }
}

// wordList に単語Barの候補を設定し，
// numWordList を求める。
// numWordList は単語数に一致しなければならない。

int matInvest[M][N];            // 1:調査した, 0:未調査
struct st_nextInvest {
  int row;
  int col;
} nextInvest[100];
int idxNextInvest;
int numNextInvest;
int padright( int row, int col)
{
  int n = 0;
  // 文字列が続く限り調査対象に加える。
  // 既に調査済みの場合加えない。
  while( col < N && mat[row][col]) {
    n++;
    if( !matInvest[row][col]) {
      // 未調査の地点です。
      nextInvest[numNextInvest].row = row;
      nextInvest[numNextInvest].col = col;
      numNextInvest++;
    }
    col++;
  }
  return n;
}
int padlow( int row, int col)
{
  int n = 0;
  while( row < M && mat[row][col]) {
    n++;
    if( !matInvest[row][col]) {
      // 未調査の地点です。
      nextInvest[numNextInvest].row = row;
      nextInvest[numNextInvest].col = col;
      numNextInvest++;
    }
    row++;
  }
  return n;
}
YesNo exist( int row, int col, int pmrow, int pmcol)
{
  row += pmrow;
  col += pmcol;
  if( row < 0) return NO;
  if( col < 0) return NO;
  if( row >= M) return NO;
  if( col >= N) return NO;
  if( mat[row][col]) return YES;
  return NO;
}
void pickWordBar( int idx)
{
  int row, col;
  row = nextInvest[idx].row;
  col = nextInvest[idx].col;
  if( matInvest[row][col]) {
    // この位置は既に調査済みである。
    return;
  }
  matInvest[row][col] = 1;// 調査済みに変更
  // この位置が単語の先頭か調べる。
  // 単語の先頭なら単語を抽出する。
  // 横方向と縦方向を調べる。
  if( !exist(row,col,0,-1) && exist(row,col,0,+1)) {
    // 横方向の単語の先頭。
    wordList[numWordList].row = row;
    wordList[numWordList].col = col;
    wordList[numWordList].direction = 1;
    wordList[numWordList].col = col;
    wordList[numWordList].len = padright(row,col);
    numWordList++;
  }
  if( !exist(row,col,-1,0) && exist(row,col,+1,0)) {
    // 縦方向の単語の先頭。
    wordList[numWordList].row = row;
    wordList[numWordList].col = col;
    wordList[numWordList].direction = 2;
    wordList[numWordList].col = col;
    wordList[numWordList].len = padlow(row,col);
    numWordList++;
  }
  else {
    // 単語の先頭ではない。
  }
}
void evalProblemMatrix()
{
  int row, col;
  for( row=0; row < M; row++) {
    for( col=0; col< N; col++) {
      if( mat[row][col]) matInvest[row][col] = 0; // 未調査
      else matInvest[row][col] = 1; // 文字の無いところは調査済みと見なす
    }
  }
  for( row=0; row < M; row++) {
    for( col=0; col< N; col++) {
      if( matInvest[row][col] == 0) {
        // 未調査地点を調査する。
        idxNextInvest = numNextInvest = 0;
        nextInvest[numNextInvest].row = row;
        nextInvest[numNextInvest].col = col;
        numNextInvest++;
        while( idxNextInvest < numNextInvest) {
          pickWordBar( idxNextInvest);
          idxNextInvest++;
        }
      }
    }
  }
}

// 以下test3.cpp で追加
int matCode[M][N];              // 文字
int matCount[M][N];             // 文字上書き数

void dumpGoal()
{
  int row, col;
  char buf[2048];
  ps( "----------------------------------------------------------------------\n");
  for( row=0; row< rows; row++) {
    for( col=0; col< columns; col++) {
      if( mat[row][col] == 0) {
        if( matCode[row][col]) {
          ps( "★");            // ここに文字は設定できないはずなのに設定されている
        }
        else {
          ps( "■");
        }
      }
      else if( matCode[row][col]) {
        char c1, c2;
        c1 = matCode[row][col]>>8;
        c2 = matCode[row][col]&0xFF;
        ps( "%c%c", c1, c2);
      }
      else {
        ps( "□");
      }
    }
    ps( "\n");
  }
}
void reset( int row, int col, int pmrow, int pmcol, int L)
{
  //ps( "reset(row:%d,col:%d,pmrow:%d,pmcol:%d,L:%d)\n", row, col, pmrow, pmcol, L);
  while( L--> 0) {
    matCount[row][col]--;
    // 文字を取り除いた結果，そこに文字が無くなったら文字を取り除く。
    if( matCount[row][col] == 0) matCode[row][col] = NIL;
    row += pmrow;
    col += pmcol;
  }
}
void solveProblem( int idxWordList)
{
  if( idxWordList >= numWordList) {
    ps( "Find GOAL\n");
    dumpGoal();
    // 解答文字列は
    for( int i=0; i< numSolve; i++) {
      char c1, c2;
      int row = solve[i].row, col = solve[i].col;
      c1 = matCode[row][col]>>8;
      c2 = matCode[row][col]&0xFF;
      ps( "%c%c", c1, c2);
    }
    ps( "\n");
    int numUnused = 0;
    for( i=0; i< numWordDic; i++) {
      if( wordDic[i].used == NO) {
        if( !numUnused) ps( "未使用単語が見つかりました\n");
        numUnused++;
        ps( "%s\n", wordDic[i].s.c_str());
      }
    }
    return; //exit(0);
  }
  int row, col, direction, len;
  row = wordList[idxWordList].row;
  col = wordList[idxWordList].col;
  direction = wordList[idxWordList].direction;
  len = wordList[idxWordList].len;
  int pos = wordIndex[len].pos; // 同じ長さの単語一覧
  int num = wordIndex[len].num;
  int p;
  jap chr;
  cstring s;
  int pmrow = 0, pmcol = 0;
  if( direction == 1) {
    pmcol = 1;
  }
  else if( direction == 2) {
    pmrow = 1;
  }
  else {
    pe( "プログラムエラー\n");
  }
  for( int i=0; i< num; i++) {
    p = pos + i;
    if( wordDic[p].used) {
      // 既にこの単語は利用されているので利用することが出来ない。
    }
    else {
      // この単語を選択する。
      // 但し選択できないことがあるので調べる必要がある。
      // 念のため長さチェック
      if( wordDic[p].len != len) { pe( "単語の長さが違う(期待単語長:%d,実単語長:%d)\n", len, wordDic[p].len);}
      // この単語を矩形内に設定して既に設定してある文字と不具合が生じなければ置くことが出きる。
      s = wordDic[p].s.c_str();
      //ps( "[%2d][%2d]%s : (%s) Len:%d\n", row, col, direction==1?"横":"縦", s, len);
      int L = len;
      int rowx = row, colx = col;
      for( int j=0; j< L; j++) {
        chr = getjap(s);
        if( matCode[rowx][colx] == 0 ||
            matCode[rowx][colx] == chr) {
          matCode[rowx][colx] = chr;
          matCount[rowx][colx]++;
        }
        else {
          // 既に違う文字が配置されていたのでここにこの単語を置くことが出来ない。
          // 既に置いてしまった分を取り消す。
          //ps( "[%2d][%2d] : 既に置かれている文字(%x)と違う文字(%x)が出現した\n", rowx, colx, matCode[rowx][colx], chr);
          reset( rowx-pmrow, colx-pmcol, -pmrow, -pmcol, j);
          break;
        }
        rowx += pmrow;
        colx += pmcol;
      }
      // 置くことが出来たら次の単語を置く努力をする。
      if( j == L) {
        wordDic[p].used = YES;
        solveProblem( idxWordList+1);
        wordDic[p].used = NO;
        // バックトラックして帰ってきたらここで置いた単語を取り除く。
        //ps( "バックトラックしてきた\n");
        reset( row, col, pmrow, pmcol, len);
      }
    }
  }
}

int main( int argc, cstring argv[])
{
  Option opt(argc,argv);
  cstring fnProblem = opt.argv(0);
  readProblem( fnProblem);
  evalProblemMatrix();
  dumpMat();
  solveProblem( 0/*単語*/);
  return 0;
}