/***************************************
 * データ構造とアルゴリズム
 * レポート課題 2-1 
 * ○×ゲーム サンプルプログラム
 ***************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node {
  int data;
  struct node* next;
};

/*============================================
  メニュー表示 
  ============================================*/
void print_menu(){
  printf("+-------- O X ゲーム --------+\n");
  printf("| ゲームを先攻で開始する: 1  |\n");
  printf("| ゲームを後攻で開始する: 2  |\n");
  printf("| やめる:                 0  |\n");
  printf("+----------------------------+\n");
}

/*===========================================
   ゲーム盤の表示 

   ※ゲーム盤での数字の意味
     1 = @, 2 = X, 0 = 未選択
  ===========================================*/
void print_board(int board[3][3], int order){
  int i, j;

  printf("\n\n");
  printf(order == 1 ? "あなた:@, コンピュータ:X \n" 
	            : "あなた:X, コンピュータ:@\n");
  printf("+---+---+---+\n");
  for ( i = 0; i < 3; i++ ){
    for ( j = 0; j < 3; j++ ){
      switch ( board[i][j] ){
      case 0 : 
	printf("| %1d ", (i*3) + j+1);
	break;
      case 1 : 
	printf("| @ ");
	break;
      case 2 : 
	printf("| X ");
	break;
      }
    }
    printf("|\n");
    printf("+---+---+---+\n");
  }
}

/*=========================================
  ゲームクリアを判定する 

  引数 board[3][3] : OXのゲーム盤
  戻り値: 1 = 終了，0 = 続行可
  =========================================*/
int is_cleared(int board[3][3]){
  int i, j;

  for ( i = 0; i < 3; i++ ){
    if ( board[i][0] == board[i][1] && board[i][0] == board[i][2] 
	 && board[i][0] != 0 ){
      return 1;
    }
  }

  for ( j = 0; j < 3; j++ ){
    if ( board[0][j] == board[1][j] && board[0][j] == board[2][j] 
	 && board[0][j] != 0 ){
      return 1;
    }
  }

  if ( board[0][0] == board[1][1] && board[0][0] == board[2][2] 
       && board[0][0] != 0 ){
    return 1;
  }

  if ( board[0][2] == board[1][1] && board[0][2] == board[2][0] 
       && board[0][2] != 0 ){
    return 1;
  }

  return 0;
}

/*=========================================
  引き分けを判定する 

  引数 board[3][3] : OXのゲーム盤
  戻り値: 1 = 引き分け，0 = 続行可
  =========================================*/
int is_draw(int board[3][3]){
  int i, j;
  for ( i = 0; i < 3; i++ ){
    for ( j = 0; j < 3; j++ ){
      if ( board[i][j] == 0 ){
	return 0;
      }
    }
  }
  return 1;
}

/*===============================================
   ゲーム盤に値を入れる

   position: 位置（1-9）
   mark: 代入する値 (0,1,2)
   ===============================================*/
void set(int board[3][3], int position, int mark){
  if ( position > 0 && position < 10 ){
    board[(position-1)/3][(position-1)%3] = mark;
  }
}


/*===============================================
   ゲーム盤で指定された位置にOXを書けるか調べる

   position: 位置（1-9）
   戻り値: 可能なら 1，不可能なら 0
   ===============================================*/
int is_empty(int board[3][3], int position){
  if ( position > 0 && position < 10 ){
    if ( board[(position-1)/3][(position-1)%3] == 0 ){
      return 1;
    }
  }
  return 0;
}


/*===========================================
   選択した場所（1-9）をスタックに push する
   ===========================================*/
void push( struct node* sp, int data ){
  /*--------------------------------
        この部分は自分で作ること
    -------------------------------*/
}

/*=================================================
   スタックから過去に選択した場所（1-9）を pop する
   =================================================*/
int pop( struct node* sp ){
  /*--------------------------------
        この部分は自分で作ること
    -------------------------------*/  
  return -1;
}


int main(void){
  int i, action, turn;
  int board[3][3];
  struct node* sp;

  /* 1 個目のノードはダミーノードとしておく 
     ※情報工学実験 I のテキストを参照      */
  sp = malloc( sizeof(struct node) );
  sp->next = NULL;

  /* 乱数の種を現在時刻で決めておく */
  srand((unsigned) time(NULL));

  /* ゲーム開始のメッセージと選択 */
  print_menu();
  while (1){
    printf(" [数字を入力して下さい: 0,1,2] > ");
    scanf("%d", &action); 
    if ( action == 0 ){
      printf("終了します．\n\n\n");
      return 0;
    }
    if ( action > 0 && action <= 2 ){
      break;
    }
  }

  /* ゲームの初期化 */
  for ( i = 1; i <= 9; i++ ){
    set(board, i, 0);
  }
  print_board(board, action);

  /* ゲームの進行 */
  /* turn は現在のプレイヤー: 1 は先手，2 は後手 */
  turn = 1; 
  while ( !is_cleared(board) && !is_draw(board) ){
    int put;

    /* action には最初に先手と後手どちらを選んだかが入っている */
    if ( turn == action ){ /* あなたの番 */
      printf(" [選択するマスの数字を入力して下さい: 1--9]\n");
      printf(" （「待った」をかけるときは -1）\n");
      printf(" > ");
      scanf("%d", &put);
      if ( put == -1 ){ /* 待ったをかけたとき */
	int pre1, pre2;
	pre1 = pop(sp); /* 直前にコンピュータが置いた位置 */
	pre2 = pop(sp); /* 直前にあなたが置いた位置 */
	set(board, pre1, 0);
	set(board, pre2, 0);
	print_board(board, action);
      }
    }
    else{ /* コンピュータの番 */
      put = (rand() % 9) + 1;
    }
    
    /* 入力された手が有効か調べる */
    if ( is_empty(board, put) ){
      push(sp, put);
      set(board, put, turn);
    }
    else{
      /* 無効ならば while の先頭に戻ってやり直し */
      continue;
    }

    printf("\n*** ");
    if ( turn == action ){
      printf("あなた");
    }
    else{
      printf("コンピュータ");
    }
    printf("は %d を選択しました ***", put);
    print_board(board, action);
    
    if ( is_cleared(board) ){
      if ( turn == action ){
	printf("\n\nおめでとうございます．あなたの勝ちです！\n");
      }
      else{
	printf("\n\n残念でした．あなたの負けです...\n");
      }
      /*--------------------------------
	（この部分は自分で作ること）
	あなたとコンピュータがそれぞれ
	どういう順番にマスを選んでいった
	のか，その履歴を表示させる
	-------------------------------*/  
    }
    else if ( is_draw(board) ){
      printf("\n\n引き分けです．\n");
    }

    /* 次のターンへ */
    if ( turn == 1 ){
      turn = 2;
    }
    else{
      turn = 1;
    }
  }

  return 0;
}