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

#define     BOARD_SIZE      3   // 盤の大きさ
#define     SQUARE_COUNT    9   // すべてのマスの数

/**************************************************
* 盤のマス等、白、黒、その他を表す
**************************************************/
typedef enum _HP_DEFS
{
    HPD_NONE,   // 盤外、未定を表す
    HPD_BLACK,  // 黒を表す
    HPD_WHITE,  // 白を表す
    HPD_EMPTY   // 空き
}HP_DEFS;


/////////////////////////////////////////////////////////////////////
//  盤のマスを示すクラス
/////////////////////////////////////////////////////////////////////
class HpPoint
{
public:
    int file;   // 左を0とした横方向
    int rank;   // 下を0とした縦方向

public:

    /////////////////////////////////////////////////////////////////
    // コンストラクタ
    /////////////////////////////////////////////////////////////////
    HpPoint()
    {
        file = -1;
        rank = -1;
    }

    /////////////////////////////////////////////////////////////////
    // コンストラクタ
    //
    // f：横方向位置
    // r：縦方向位置
    /////////////////////////////////////////////////////////////////
    HpPoint(int f, int r)
    {
        file = f;
        rank = r;
    }

    /////////////////////////////////////////////////////////////////
    // 左右反対のHpPointを取得する
    //
    // return：左右反対のHpPoint
    /////////////////////////////////////////////////////////////////
    HpPoint Mirror()    const
    {
        HpPoint mirror(file, rank);

        if (mirror.file == 0)
            mirror.file = 2;
        else if (mirror.file == 2)
            mirror.file = 0;

        return mirror;
    }

    /////////////////////////////////////////////////////////////////
    // 文字列にする
    //
    // pText：文字列へのポインタ
    /////////////////////////////////////////////////////////////////
    void ToText(char* pText)    const
    {
        pText[0] = file + 'a';  // 左から a,b,c
        pText[1] = rank + '1';  // 下から 1,2,3
        pText[2] = 0;
    }
};

/////////////////////////////////////////////////////////////////////
// 盤面を表すクラス
/////////////////////////////////////////////////////////////////////
class HpBoard
{
protected:
    HP_DEFS mSquares[BOARD_SIZE][BOARD_SIZE];   // 盤のマス

public:
    /////////////////////////////////////////////////////////////////
    // コンストラクタ
    /////////////////////////////////////////////////////////////////
    HpBoard()
    {
        // 盤の初期状態を作成する
        for (int file = 0; file < BOARD_SIZE; file++)
        {
            SetSquare(HpPoint(file, 2), HPD_BLACK); // 黒のポーン
            SetSquare(HpPoint(file, 1), HPD_EMPTY); // 空き
            SetSquare(HpPoint(file, 0), HPD_WHITE); // 白のポーン
        }
    }

    /////////////////////////////////////////////////////////////////
    // すべてのマスの位置を取得する
    //
    // apt：HP_POINTの配列（要素数はSQUARE_COUNT）
    /////////////////////////////////////////////////////////////////
    static void GetAllPoints(HpPoint apt[])
    {
        int n = 0;

        for (int rank = 0; rank < BOARD_SIZE; rank++)
        {
            for (int file = 0; file < BOARD_SIZE; file++)
                apt[n++] = HpPoint(file, rank);
        }
    }

    /////////////////////////////////////////////////////////////////
    // 指定されたマスの状態を取得する
    //
    // pt：マスの位置を表すHpPoint
    // return：マスの状態
    /////////////////////////////////////////////////////////////////
    HP_DEFS GetSquare(const HpPoint& pt)    const
    {
        return GetSquare(pt.file, pt.rank);
    }

    /////////////////////////////////////////////////////////////////
    // 指定されたマスの状態を取得する
    //
    // file：横方向の位置
    // rank：縦方向の位置
    // return：マスの状態
    /////////////////////////////////////////////////////////////////
    HP_DEFS GetSquare(int file, int rank)   const
    {
        if (0 <= file && file < BOARD_SIZE
            && 0 <= rank && rank < BOARD_SIZE)
        {
            return mSquares[file][rank];
        }
        else{
            return HPD_NONE;
        }
    }

    /////////////////////////////////////////////////////////////////
    // 指定されたマスの状態を設定する
    //
    // pt：マスの位置を表すHpPoint
    // pawn：マスの状態
    /////////////////////////////////////////////////////////////////
    void SetSquare(const HpPoint& pt, HP_DEFS pawn)
    {
        return SetSquare(pt.file, pt.rank, pawn);
    }

    /////////////////////////////////////////////////////////////////
    // 指定されたマスの状態を設定する
    //
    // file：横方向の位置
    // rank：縦方向の位置
    // pawn：マスの状態
    /////////////////////////////////////////////////////////////////
    void SetSquare(int file, int rank, HP_DEFS pawn)
    {
        if (0 <= file && file < BOARD_SIZE
            && 0 <= rank && rank < BOARD_SIZE)
        {
            mSquares[file][rank] = pawn;
        }
    }

    /////////////////////////////////////////////////////////////////
    // 盤の状態を表示する
    /////////////////////////////////////////////////////////////////
    void Show() const
    {
        printf("\n");

        for (int rank = BOARD_SIZE - 1; rank >= 0; rank--)
        {
            printf("\n   +---+---+---+");
            printf("\n %d |", rank + 1);

            for (int file = 0; file < BOARD_SIZE; file++)
            {
                if (GetSquare(file, rank) == HPD_BLACK)
                    printf(" ○|");
                else if (GetSquare(file, rank) == HPD_WHITE)
                    printf(" ●|");
                else if ((rank % 2) == (file % 2))
                    printf(":::|");
                else
                    printf("   |");
            }

            if (rank == 2)
                printf("      7  8  9");
            else if (rank == 1)
                printf("      4  5  6");
            else if (rank == 0)
                printf("      1  2  3");
        }

        printf("\n   +---+---+---+");
        printf("\n     a   b   c\n");
    }

    /////////////////////////////////////////////////////////////////
    // 指定された位置のポーンが動けるかどうか
    //
    // pt：調べるマス
    // return：true 動ける、false 動けない
    /////////////////////////////////////////////////////////////////
    bool IsMoveablePawn(const HpPoint& pt)
    {
        int dir;    // 進む方向
        int opp;    // 対戦相手の駒

        if (GetSquare(pt) == HPD_WHITE)
        {
            dir = 1;
            opp = HPD_BLACK;
        }
        else if (GetSquare(pt) == HPD_BLACK)
        {
            dir = -1;
            opp = HPD_WHITE;

        }
        else{
            return false;
        }

        if (GetSquare(pt.file, pt.rank + dir) == HPD_EMPTY)
            return true;    // １マス前が空
        else if (GetSquare(pt.file - 1, pt.rank + dir) == opp)
            return true;    // 斜め前に相手の駒がある
        else if (GetSquare(pt.file + 1, pt.rank + dir) == opp)
            return true;    // 反対の斜め前に相手の駒がある
        else
            return false;
    }

    /////////////////////////////////////////////////////////////////
    // 駒の移動が有効であるかどうかを調べる
    //
    // from：移動元
    // to：移動先
    // return：true 有効、false 無効
    /////////////////////////////////////////////////////////////////
    bool IsValidMove(const HpPoint& from, const HpPoint& to)
    {
        int     df = to.file - from.file;
        int     dr = to.rank - from.rank;

        if (GetSquare(from) == HPD_WHITE)
        {
            // 動かす駒が白

            if (GetSquare(to) == HPD_EMPTY && df == 0 && dr == 1)
                return true;    // １マス前に動ける
            else if (GetSquare(to) == HPD_BLACK && (df == 1 || df == -1) && dr == 1)
                return true;    // 斜め前に動ける
        }
        else if (GetSquare(from) == HPD_BLACK)
        {
            // 動かす駒が黒

            if (GetSquare(to) == HPD_EMPTY && df == 0 && dr == -1)
                return true;    // １マス前に動ける
            else if (GetSquare(to) == HPD_WHITE && (df == 1 || df == -1) && dr == -1)
                return true;    // 斜め前に動ける
        }

        return false;
    }

    /////////////////////////////////////////////////////////////////
    // 勝敗を確認する
    //
    // next：次が白番か、黒番か
    // return：HPD_BLACK 黒の勝ち、HPD_WHITE 白の勝ち、HPD_EMPTY 未定
    /////////////////////////////////////////////////////////////////
    HP_DEFS CheckFinish(HP_DEFS next)
    {
        HpPoint all[SQUARE_COUNT];
        int cntWhite = 0;
        int cntBlack = 0;

        // ３列目に駒があるか /////////////////////////
        for (int file = 0; file < BOARD_SIZE; file++)
        {
            if (GetSquare(file, BOARD_SIZE - 1) == HPD_WHITE)
                return HPD_WHITE;
            else if (GetSquare(file, 0) == HPD_BLACK)
                return HPD_BLACK;
        }

        // 動ける駒の数 ///////////////////////////////

        GetAllPoints(all);

        for (int sq = 0; sq < SQUARE_COUNT; sq++)
        {
            if (IsMoveablePawn(all[sq]))
            {
                if (HPD_WHITE == GetSquare(all[sq]))
                    cntWhite++;
                else if (HPD_BLACK == GetSquare(all[sq]))
                    cntBlack++;
            }
        }

        if (next == HPD_WHITE && cntWhite == 0)
            return HPD_BLACK;   // 次が白番で動かせる駒が無い
        else if (next == HPD_BLACK && cntBlack == 0)
            return HPD_WHITE;   // 次が黒番で動かせる駒が無い

        return HPD_EMPTY;   // 勝敗未定
    }

};

/////////////////////////////////////////////////////////////////////
//  盤の状態を表すクラス
/////////////////////////////////////////////////////////////////////
class HpBoardMove : public HpBoard
{
protected:
    HpPoint mFrom;  // 駒の移動元
    HpPoint mTo;    // 駒の移動先

public:

    /////////////////////////////////////////////////////////////////
    // 駒の移動を設定する
    //
    // rFrom：移動元
    // rTo：移動先
    /////////////////////////////////////////////////////////////////
    void SetMove(const HpPoint& rFrom, const HpPoint& rTo)
    {
        mFrom = rFrom;
        mTo = rTo;
    }

    /////////////////////////////////////////////////////////////////
    // 移動元のマスを取得する
    //
    // return：移動元のマスの位置
    /////////////////////////////////////////////////////////////////
    const HpPoint& GetFrom()
    {
        return mFrom;
    }

    /////////////////////////////////////////////////////////////////
    // 移動先のマスを取得する
    //
    // return：移動先のマスの位置
    /////////////////////////////////////////////////////////////////
    const HpPoint& GetTo()
    {
        return mTo;
    }

    /////////////////////////////////////////////////////////////////
    // operator ==
    /////////////////////////////////////////////////////////////////
    bool operator ==(const HpBoardMove& bd)const
    {
        HpPoint all[SQUARE_COUNT];

        GetAllPoints(all);

        for (int i = 0; i < SQUARE_COUNT; i++)
        {
            if (this->GetSquare(all[i]) != bd.GetSquare(all[i]))
                return false;
        }

        if (this->mFrom.file != bd.mFrom.file || this->mFrom.rank != bd.mFrom.rank
            || this->mTo.file != bd.mTo.file || this->mTo.rank != bd.mTo.rank)
            return false;

        return true;
    }

    /////////////////////////////////////////////////////////////////
    // 移動元から移動先へ、駒を移動する
    /////////////////////////////////////////////////////////////////
    void MovePawn()
    {
        SetSquare(mTo, GetSquare(mFrom));
        SetSquare(mFrom, HPD_EMPTY);
    }

    /////////////////////////////////////////////////////////////////
    // 左右反対の盤の状態を取得する
    //
    // return：左右反対のHpBoardMove
    /////////////////////////////////////////////////////////////////
    HpBoardMove MakeMirror()    const
    {
        HpPoint all[SQUARE_COUNT];
        HpBoardMove mirror;

        // 左右反対の盤の状態を作成する ///////////////
        mirror.mFrom = mFrom.Mirror();
        mirror.mTo = mTo.Mirror();

        GetAllPoints(all);

        for (int i = 0; i < SQUARE_COUNT; i++)
            mirror.SetSquare(all[i], GetSquare(all[i].Mirror()));

        return mirror;
    }
};

/////////////////////////////////////////////////////////////////////
// 盤の状態のリスト
/////////////////////////////////////////////////////////////////////
class HpBoardList
{
private:
    HpBoardMove*    mpBoad;     // 配列
    int             mCount;     // 要素数

public:
    /////////////////////////////////////////////////////////////////
    // コンストラクタ
    /////////////////////////////////////////////////////////////////
    HpBoardList()
    {
        mpBoad = NULL;
        mCount = 0;
    }

    /////////////////////////////////////////////////////////////////
    // デストラクタ
    /////////////////////////////////////////////////////////////////
    ~HpBoardList()
    {
        delete[] mpBoad;    // 配列をデリート
    }

    /////////////////////////////////////////////////////////////////
    // 要素の追加
    //
    // bd：追加するHpBoardMove
    /////////////////////////////////////////////////////////////////
    void Add(HpBoardMove bd)
    {
        // 新しい配列を作成する
        HpBoardMove* pNewList = new HpBoardMove[mCount + 1];

        // 元の要素をコピーする
        for (int i = 0; i < mCount; i++)
            pNewList[i] = mpBoad[i];

        // 元の配列を追加
        delete[] mpBoad;

        // 新しい配列を変数に保持
        mpBoad = pNewList;

        // 追加する要素を配列の最後に代入
        mpBoad[mCount++] = bd;
    }

    /////////////////////////////////////////////////////////////////
    // 負けの状態を検索する（左右対称も含んで）
    //
    // rbd：検索するHpBoardMove
    /////////////////////////////////////////////////////////////////
    bool Exist(const HpBoardMove& rbd)  const
    {
        HpBoardMove mirror = rbd.MakeMirror();  // 左右反対の盤面

        // 負けの手から探す ///////////////////////////
        for (int i = 0; i < mCount; i++)
        {
            if (rbd == mpBoad[i])
                return true;

            if (mirror == mpBoad[i])
                return true;
        }

        return false;
    }

private:
    HpBoardList(const HpBoardList&);    // コピー・コンストラクタ
};


/////////////////////////////////////////////////////////////////////
// ゲーム
/////////////////////////////////////////////////////////////////////
class Game
{
private:
    HpBoardList&    mDefeatList;    // 負けに至った手のリスト

public:
    /////////////////////////////////////////////////////////////////
    // コンストラクタ
    //
    // rList：負けに至った手のリスト
    /////////////////////////////////////////////////////////////////
    Game(HpBoardList& rList) : mDefeatList(rList)
    {
    }

    /////////////////////////////////////////////////////////////////
    // マッチ箱の手を決定する
    //
    // pbd：現在の盤の状態
    // borw：黒番か白番か
    // return：true 打った false リザイン
    /////////////////////////////////////////////////////////////////
    bool MatchBoxTurn(HpBoardMove* pbd, HP_DEFS borw)
    {
        HpPoint allsq[SQUARE_COUNT];

        // すべてのマスの位置を取得する
        HpBoard::GetAllPoints(allsq);

        // ランダムに打つよう、配列の順番を変更する
        for (int i = 0; i < 20; i++)
        {
            // 任意の２つのマスの配列内の順番を入れ替える
            int     p = rand() % SQUARE_COUNT;
            int     q = rand() % SQUARE_COUNT;

            if (p != q)
            {
                HpPoint t = allsq[p];
                allsq[p] = allsq[q];
                allsq[q] = t;
            }
        }

        // 有効な手を探索する
        for (int i = 0; i < SQUARE_COUNT; i++)
        {
            if (pbd->GetSquare(allsq[i]) != borw)
                continue;   // 手番の駒が無ければ次へ

            for (int j = 0; j < SQUARE_COUNT; j++)
            {
                pbd->SetMove(allsq[i], allsq[j]);

                // 有効な手であり、負けの手に含まれていなければOK!
                if (pbd->IsValidMove(allsq[i], allsq[j]) && !mDefeatList.Exist(*pbd))
                {
                    char    szFrom[10];
                    char    szTo[10];

                    pbd->GetFrom().ToText(szFrom);
                    pbd->GetTo().ToText(szTo);

                    printf("\nマッチ箱： %s を %s へ", szFrom, szTo);

                    return true;
                }
            }
        }

        // 打つ手が無ければリザイン

        printf("\nリザインします。");

        return false;   // リザイン
    }

    /////////////////////////////////////////////////////////////////
    // ガイドを表示してマスの位置を入力する
    //
    // szGuide：ガイド文字列
    // return：入力されたマスの位置
    /////////////////////////////////////////////////////////////////
    HpPoint InputSquarePoint(char* szGuide)
    {
        for (;;)
        {
            printf(szGuide);

            int ch = _getche();

            switch (ch)
            {
            case '7':
                return HpPoint(0, 2);
            case '8':
                return HpPoint(1, 2);
            case '9':
                return HpPoint(2, 2);
            case '4':
                return HpPoint(0, 1);
            case '5':
                return HpPoint(1, 1);
            case '6':
                return HpPoint(2, 1);
            case '1':
                return HpPoint(0, 0);
            case '2':
                return HpPoint(1, 0);
            case '3':
                return HpPoint(2, 0);
            }
        }

        return HpPoint(-1, -1);
    }

    /////////////////////////////////////////////////////////////////
    //  プレイヤーの手を決定する
    //
    // pbd：現在の盤の状態
    // borw：黒番か白番か
    /////////////////////////////////////////////////////////////////
    void PlayerTurn(HpBoardMove* pbd, HP_DEFS borw)
    {
        HpPoint from, to;

        // 動かす駒の入力
        for (;;)
        {
            from = InputSquarePoint("\n駒を選んでください(1～9)：");

            if (borw == pbd->GetSquare(from) && pbd->IsMoveablePawn(from))
                break;
            else
                printf("\n動かせる駒がありません");
        }

        // どこへ動かすかを入力
        for (;;)
        {
            to = InputSquarePoint("\nどこに動かしますか？(1～9)：");

            if (pbd->IsValidMove(from, to))
                break;
            else
                printf("\nそこには動かせません");
        }

        // 駒の移動を設定する
        pbd->SetMove(from, to);
    }
};

/////////////////////////////////////////////////////////////////////
//  main関数
/////////////////////////////////////////////////////////////////////
void main(void)
{
    HpBoardList     defeats;        // 負けの手を保持する配列
    HP_DEFS player = HPD_WHITE;     // プレイヤーの色
    HP_DEFS matchbox = HPD_BLACK;   // マッチ箱の色
    int reply;                      // ユーザー入力を受け取る変数

    srand((unsigned int)time(0));   // 乱数の初期化

    do
    {
        Game    game(defeats);

        HpBoardMove     board;                  // 現在の盤の状態
        HpBoardMove     lastMatchBoxMove;       // マッチ箱の最後の手
        int             cntMatchBoxMove = 0;    // マッチ箱の手数
        HP_DEFS     winner = HPD_NONE;  // 勝者
        HP_DEFS     turn = HPD_WHITE;   // 現在の手番

        board.Show();

        while (winner != HPD_WHITE && winner != HPD_BLACK)
        {
            if (turn == player)
            {
                // プレイヤーのターン

                game.PlayerTurn(&board, player);
            }
            else
            {
                // マッチ箱のターン

                if (game.MatchBoxTurn(&board, matchbox))
                {
                    lastMatchBoxMove = board;
                    cntMatchBoxMove++;
                }
                else
                {
                    // リザインした場合
                    winner = player;
                    break;
                }
            }

            // 駒を移動
            board.MovePawn();

            // 盤面を表示
            board.Show();

            // 次のターンへ
            if (turn == HPD_BLACK)
                turn = HPD_WHITE;
            else
                turn = HPD_BLACK;

            // 勝敗の確認
            winner = board.CheckFinish(turn);
        }

        if (winner == HPD_WHITE)
            printf("\n白の勝ちです。\n");
        else if (winner == HPD_BLACK)
            printf("\n黒の勝ちです。\n");

        if (winner != matchbox && cntMatchBoxMove > 0)
            defeats.Add(lastMatchBoxMove);

        printf("終了する場合は'Q'、続ける場合は他のキーを押してください");
        reply = _getche();
    } while (!(reply == 'q' || reply == 'Q'));
}