#include <stdio.h>

//#define DEBUG    1

#define DIM      3

#define SYM_X    'X'
#define SYM_O    'O'
#define SYM_SPC  '_'

#define DOWN     -1
#define NONE     0
#define UP       1

#define VALID(ch)    ((ch == SYM_X) || (ch == SYM_O) || (ch == SYM_SPC))
#define EDGE(pos)    (!pos || (pos == DIM - 1))

// Read a TicTacToe board from stdin and store it in 'board'.
// User is prompted for the state of each board cell.
// In case the input is not recognized, an error message is
// issued and the user is repeatedly prompted until a
// valid entry is given.
void readBoard(char board[DIM][DIM])
{
    unsigned i, j;

    for (i = 0; i < DIM; i++)
    {
        for (j = 0; j < DIM; j++)
        {
            printf("Row %u Col %u? ", i, j);
            do
            {
                board[i][j] = getchar();
                if (board[i][j] != '\n' && !VALID(board[i][j]))
                {
                    printf("ERROR: Read '%c'.  Try again.\n", board[i][j]);
                }
            } while (!VALID(board[i][j]));
        }
    }
}

// Prints the contents of the TicTacToe 'board' to stdout.
void printBoard(char board[DIM][DIM])
{
    unsigned i, j;

    printf("\n");
    for (i = 0; i < DIM; i++)
    {
        for (j = 0; j < DIM; j++)
        {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
}

// Checks if there is a winner on the 'board'.
// If there is, it will be announced via stdout.  Otherwise, nothing is printed.
// Starts from row 'start_row' and column 'start_col'.
// The subsequent positions are obtained by repeatedly incrementing
// the row index by 'row_delta' and the column index by 'col_delta'.
void checkVector(char board[DIM][DIM], unsigned start_row, unsigned start_col,
unsigned row_delta, unsigned col_delta)
{
    unsigned i, j, count;
    char tracking = NONE;

#ifdef DEBUG
    printf("  Checking (%u, %u) going in direction (%d, %d) ", start_row,
        start_col, row_delta, col_delta);
#endif
    if (board[start_row][start_col] == SYM_SPC)
    {
        // Vector contains a space.  A winner cannot exist in this vector.
        return;
    }

    for (i = start_row, j = start_col, count = 0; i >= 0 && j >= 0 &&
        i < DIM && j < DIM; i = i + row_delta, j = j + col_delta,
        count++)
    {
#ifdef DEBUG
        printf("%c ", board[i][j]);
#endif
        if (tracking == NONE)
        {
            // The character we find in the starting position determines
            // which character we must look for.  E.g., if this is an 'X'
            // then all the subsequent entries must also be an 'X', or the
            // current vector does not contain a winning entry.
            tracking = board[i][j];
            continue;
        }

        if (tracking != board[i][j])
        {
            // We expected the character 'tracking', but found another
            // character instead.  This is not a winning position, and
            // we can abandon the search.
#ifdef DEBUG
            printf("x\n");
#endif
            return;
        }
    }

    if (count == DIM)
    {
        // We have looked at all 'DIM' cells in a row, and found
        // the same character in each one of them.  We have a winner!
        printf("%c wins at (%u, %u) going in direction (%d, %d)\n",
            tracking, start_row, start_col, row_delta, col_delta);
    }
#ifdef DEBUG
    else
    {
        // Looks like we started in a position that was not
        // an edge.  We have not looked at every entry.
        printf("x\n");
    }
#endif
}

// Given 'board' and starting position at ('row', 'col'), see
// if there are any winners.  For example, if we are at position
// (0,0), this function will check the column (0,0), (1,0), (2,0)
// and the row (0,1), (0,2), (0,3) and the diagonal (0,0), (1,1), (2,2)
// for winners.  If there are any, they will be announced via a
// message to stdout.  Otherwise, nothing is printed.
void checkVectors(char board[DIM][DIM], unsigned row, unsigned col)
{
    int i, j;

    // This does MANY redundant checks and needs to be cleaned up!!
    for (i = DOWN; i <= UP; i++)
    {
        for (j = DOWN; j <= UP; j++)
        {
            if (!i && !j)
            {
                // Ignore the vector (0,0).
                continue;
            }
#ifdef DEBUG
	printf(" Checking Direction Row %d Col %d\n", i, j);
#endif
            checkVector(board, row, col, i, j);
        }
    }
}

// Checks the TicTacToe board 'board' for winning positions.
// If there are any, they will be printed out to stdout.
// Otherwise, nothing is printed.
void checkBoard(char board[DIM][DIM])
{
    unsigned row, col;

    for (row = 0; row < DIM; row++)
    {
        for (col = 0; col < DIM; col++)
        {
            if (EDGE(row) || EDGE(col))
            {
		// Only need to check edges
#ifdef DEBUG
		printf("Checking Row %u Col %u\n", row, col);
#endif
                checkVectors(board, row, col);
            }
        }
    }
}

int main()
{
    char board[DIM][DIM];

    readBoard(board);
#ifdef DEBUG
    printBoard(board);
#endif
    checkBoard(board);
    
    return 0;
}