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

#define ROW_MAX 8
#define COL_MAX 8
#define PLAYER_1 'B'
#define PLAYER_2 'W'
#define INFINITY 999999
#define TRUE 1
#define FALSE 0

// Global variables
char board[ROW_MAX][COL_MAX];

// Prototypes
void InitializeBoard();
void DisplayBoard();
void UpdateBoard(int row, int col, char color, char myboard[][COL_MAX]);
void Winner();
void MoveHorizontal(int row, int col, char color, char myboard[][COL_MAX]);
void MoveVertical(int row, int col, char color, char myboard[][COL_MAX]);
void MoveOrthogonal(int row, int col, char color, char myboard[][COL_MAX]);
int CheckMove(int row, int col, char color, char myboard[][COL_MAX]);
int CheckHorizontal(int row, int col, char color, char myboard[][COL_MAX]);
int CheckVertical(int row, int col, char color, char myboard[][COL_MAX]);
int CheckOrthogonal(int row, int col, char color, char myboard[][COL_MAX]);
int Evaluator(int row, int col, char color, char myboard[][COL_MAX] );
int EvaluateBoard(char myboard[][COL_MAX]);
int GameOver(char myboard[][COL_MAX], char color);

// Main function
int main(int argc, char *argv[])
{
   int row, col;
   char color = PLAYER_1;
	
   InitializeBoard();

   while (!GameOver(board, color))
   {
      DisplayBoard();

      if (color == PLAYER_1)
         printf("Player 1 (Black)\n");
      else printf("Player 2 (White)\n");	


      printf("Please enter your next move (row col, or -1 -1 to pass):  ");
      scanf("%d %d", &row, &col);

      if ((row == -1) && (col == -1))
      {
         printf("pass\n");
         if (color == PLAYER_1)			
            color = PLAYER_2;
         else color = PLAYER_1;
      }
      else if (CheckMove(row, col, color, board) > 0)
      {
	 printf("move accepted, updating board\n");
         board[row][col] = color;
         UpdateBoard(row, col, color, board);
         if (color == PLAYER_1)			
            color = PLAYER_2;
         else color = PLAYER_1;
      }
      else printf("invalid move\n");
   }
   Winner();
}


// Determine who won the game.
void Winner()
{
   int i, j, w=0, b=0;

   for (i=0; i<ROW_MAX; i++)
   {
      for (j=0; j<COL_MAX; j++)
      {	
         if (board[i][j] == 'W')
            w++;
         if (board[i][j] == 'B')
            b++;
      }
   }

   printf("Total black = %d, white = %d\n", b, w);
   if (b > w)
      printf("Player 1 won\n");
   else if (b < w )
      printf("Player 2 won\n");
   else
      printf("Tie game\n");
}


// The game is over if there are no playable spots left
int GameOver(char myboard[][COL_MAX], char color)
{
   int i, j, spots=0;
   char opposite_color;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else opposite_color = PLAYER_1;

   for (i=0; i<ROW_MAX; i++)
   {
      for (j=0; j<COL_MAX; j++)
      {
         if ((myboard[i][j] == ' ') && (Evaluator(i, j, color, myboard) > 0))
            spots++;
         if ((myboard[i][j] == ' ') && (Evaluator(i, j, opposite_color, myboard) > 0))
            spots++;
      }
   }

   if (spots == 0)
      return(TRUE);
   else return(FALSE);
}


int Evaluator(int row, int col, char color, char myboard[][COL_MAX])
{
   int total = 0;

   total += CheckHorizontal(row, col, color, myboard);
   total += CheckVertical(row, col, color, myboard);
   total += CheckOrthogonal(row, col, color, myboard);
	
   return(total);
}


void UpdateBoard(int row, int col, char color, char myboard[][COL_MAX])
{
   MoveHorizontal( row, col, color, myboard);
   MoveVertical( row, col, color, myboard);
   MoveOrthogonal( row, col, color, myboard);
}


void MoveOrthogonal(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i, j;
   int gain = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else opposite_color = PLAYER_1;

   // Check orthogonal left down
   for (i=row+1, j=col-1; i<COL_MAX && j>=0; i++, j--)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }
	
   if (gain>0 && valid == TRUE)
   {
      for (i=row+1, j=col-1; i<COL_MAX && j>=0; i++, j--)
      {
         if (myboard[i][j] == opposite_color)
            myboard[i][j] = color;
         else if (myboard[i][j] == color)
            break;
      }
   }

   // Check orthogonal left up
   gain = 0;
   valid = FALSE;
   for (i=row-1, j=col+1; i>=0 && j<COL_MAX; i--, j++)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (gain>0 && valid == TRUE)
   {
      for (i=row-1, j=col+1; i>=0 && j<COL_MAX; i--, j++)
      {
         if (myboard[i][j] == opposite_color)
            myboard[i][j] = color;
         else if (myboard[i][j] == color)
            break;
      }
   }

   // Check orthogonal right down
   gain = 0;
   valid = FALSE;
   for (i=row+1, j=col+1; i<ROW_MAX && j<COL_MAX; i++, j++)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (gain > 0 && valid == TRUE)
   {
      for (i=row+1, j=col+1; i<ROW_MAX && j<COL_MAX; i++, j++)
      {
         if (myboard[i][j] == opposite_color)
            myboard[i][j] = color;
         else if (myboard[i][j] == color)
            break;
      }	
   }
	
   // Check orthogonal left up
   gain = 0;
   valid = FALSE;
   for (i=row-1, j=col-1; i >= 0 && j >= 0; i--, j--)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (gain>0 && valid == TRUE)
   {
      for (i = row-1, j = col-1 ; i >= 0 && j >= 0; i--, j--)
      {
         if (myboard[i][j] == opposite_color)
            myboard[i][j] = color;
         else if (myboard[i][j] == color)
            break;
      }
   }
}


void MoveVertical(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i;
   int gain = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else
      opposite_color = PLAYER_1;

   // Check up
   for (i=row+1; i<COL_MAX; i++)
   {
      if (myboard[i][col] == opposite_color)
         gain++;
      else if (myboard[i][col] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (gain>0 && valid==TRUE)
   {
      for (i = row+1; i < COL_MAX; i++)
      {
         if (myboard[i][col] == opposite_color)
            myboard[i][col] = color;
         else if (myboard[i][col] == color)
            break;
      }
   }

   // Check down
   gain = 0;
   valid = FALSE;

   for (i = row-1; i >= 0; i--)
   {
      if (myboard[i][col] == opposite_color)
         gain++;
      else if (myboard[i][col] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }
	
   if (gain > 0 && valid == TRUE )
   {
      for (i = row-1; i >= 0; i--)
      {
         if (myboard[i][col] == opposite_color)
            myboard[i][col] = color;
         else if (myboard[i][col] == color)
            break;
      }
   }
}


void MoveHorizontal(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i;
   int gain = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else
      opposite_color = PLAYER_1;

   // Check right
   for (i = col+1; i < COL_MAX; i++)
   {
      if (myboard[row][i] == opposite_color)
         gain++;
      else if (myboard[row][i] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (gain > 0 && valid == TRUE)
   {
      for (i=col+1; i<COL_MAX; i++)
      {
         if (myboard[row][i] == opposite_color)
            myboard[row][i] = color;
         else if (myboard[row][i] == color)
            break;
      }
   }

   // Check left
   gain = 0;
   valid = FALSE;
   for (i=col-1; i>=0; i--)
   {
   if (myboard[row][i] == opposite_color)
      gain++;
   else if (myboard[row][i] == color)
   {
      valid = TRUE;
      break;
   }
   else
      break;
   }

   if (gain > 0 && valid == TRUE)
   {
      for (i = col-1; i >= 0; i--)
      {
         if (myboard[row][i] == opposite_color)
            myboard[row][i] = color;
         else if (myboard[row][i] == color)
            break;
      }		
   }
}


int CheckOrthogonal(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i, j;
   int gain = 0, total = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else
      opposite_color = PLAYER_1;

   // Check orthogonal left down
   for (i = row+1, j= col -1; i < COL_MAX && j >= 0; i++, j--)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;

   // Check orthogonal left up
   valid = FALSE;
   for (i=row-1, j=col+1 ; i>=0 && j<COL_MAX; i--, j++)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;

   // Check orthogonal right down
   valid = FALSE;
   for (i=row+1, j=col+1; i<ROW_MAX && j<COL_MAX; i++, j++)
   {
      if (myboard[i][j] == opposite_color)
         gain++;
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;

   valid = FALSE;
   // Check orthogonal left up
   for (i = row-1, j = col-1 ; i >= 0 && j >= 0; i--, j--)
   {
      if (myboard[i][j] == opposite_color)
      {
         gain++;
      }
      else if (myboard[i][j] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;

   if (total>0)
      return(total);

   return(0);
}


int CheckVertical(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i;
   int gain = 0, total = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else
      opposite_color = PLAYER_1;

   // Check up
   for (i=row+1; i<COL_MAX; i++)
   {
      if (myboard[i][col] == opposite_color)
         gain++;
      else if (myboard[i][col] == color)
      {
         valid = TRUE;
         break;
      }
      else
         break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;

   // Check down
   valid = FALSE;
   for (i=row-1; i>=0; i--)
   {
      if (myboard[i][col] == opposite_color)
         gain++;
      else if (myboard[i][col] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (valid != TRUE)
      gain = 0;	

   total += gain;
   if (total > 0)
      return(total);

   return(0);
}


int CheckHorizontal(int row, int col, char color, char myboard[][COL_MAX])
{
   char opposite_color;
   int i;
   int gain = 0, total = 0;
   int valid = FALSE;

   if (color == PLAYER_1)
      opposite_color = PLAYER_2;
   else
      opposite_color = PLAYER_1;

   // Check right
   for (i = col+1; i < COL_MAX; i++)
   {
      if (myboard[row][i] == opposite_color)
         gain++;
      else if (myboard[row][i] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }
	
   if (valid != TRUE)
      gain = 0;
   total += gain;

   // Check left
   valid = FALSE;
   for (i = col-1; i >= 0; i--)
   {
      if (myboard[row][i] == opposite_color)
         gain++;
      else if (myboard[row][i] == color)
      {
         valid = TRUE;
         break;
      }
      else break;
   }

   if (valid != TRUE)
      gain = 0;
   total += gain;	
	
   if (total > 0)
      return(total);

   return(0);
}


// Check move if it is possible it return total gain
// Othewise, it returns -1
int CheckMove(int row, int col, char color, char myboard[][COL_MAX])
{
   int total = 0;

   if ((row < 0) || (col < 0) || (row >= ROW_MAX) || (col >= COL_MAX))
      return(-1);

   if (board[row][col] == ' ')
   {	
      total = Evaluator(row, col, color, myboard);

      if (total > 0)
         return(total);
      else return(-1);
   }
   else return(-1);
}


// Initialize the board
void InitializeBoard()
{
   int i, j;

   for (i=0; i<ROW_MAX; i++)
   {
      for (j=0; j<COL_MAX; j++)
      {
         if ((i==3 && j==3)  || (i==4 &&j==4))
            board[i][j] = 'W';
         else if ((i==4 && j==3) || (i==3 && j==4))
            board[i][j] = 'B';
         else
            board[i][j] = ' ';
      }
   }
}


// Display the board
void DisplayBoard()
{
   int i, j;

   printf("  ");
   for (j = 0; j < COL_MAX; j++)
      printf("%d ", j );
   printf("\n");

   for (i=0; i<ROW_MAX; i++)
   {
      printf("%d|", i);
      for (j=0; j<COL_MAX; j++)
         printf("%c|", board[i][j]);
      printf("\n");

      for (j=0; j<COL_MAX; j++)
         printf("--");
      printf("--\n");
   }
}