include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define INF 0x7FFFFFFF
#define cINF 0x7F

//Left child, Right sibling
typedef struct MultiWayIntTree {
	int value, nrChild, alpha, beta;
	struct MultiWayIntTree *left, *right, *parent;
} mw_ITree;

typedef struct MultiWayIntTreeQueue {
	mw_ITree *tree;
	struct MultiWayIntTreeQueue *next;
} mw_ITQueue;

typedef struct MultiWayMatrixTree {
	char matrix[20][20];
	struct MultiWayMatrixTree *left, *right;
} mw_MTree;

bool same(char *string1, char *string2)
{
	return !strcmp(string1, string2);
}

int Minimax(mw_ITree *tree, bool mM);

void freeIT(mw_ITree *node)
{
	if(node == NULL) {
		return;
	}
	mw_ITree *p, *p_next;
	p = node->left;
	while(p != NULL) {
		p_next = p->right;
		freeIT(p);
		p = p_next;
	}
	free(node);
}

void insert_MTree(mw_MTree *parent, mw_MTree *child)
{
	child->left = NULL; //copilul nu are alti copii... e prea mic
	child->right = NULL;//copilul inca nu stie ca are si alti frati
	if(parent->left == NULL) {
		parent->left = child;
		return;
	}
	child->right = parent->left;
	parent->left = child;
}

char RB_to_nr(char RB)
{
	//Blue = 0, Red = 1
	if(RB == 'B')
		return 0;
	if(RB == 'R')
		return 1;
	//RB == '-'
	return 8;
}

char nr_to_RB(char nr)
{
	if(nr == 1)
		return 'R';
	if(nr == 0)
		return 'B';
	//nr == 8;
	return '-';
}

void printTabs(FILE *fout, int tabs_count)
{
	int i;
	for(i = 0; i < tabs_count; ++i)
		fprintf(fout, "\t");
}

void printMatrix(FILE *fout, int N, int M, char matrix[20][20], int tabs_count)
{
	int i, j;
	int M1 = M - 1;
	for(i = 0; i < N; ++i) {
		printTabs(fout, tabs_count);
		for(j = 0; j < M1; ++j) {
			fprintf(fout, "%c ", nr_to_RB(matrix[i][j]));
		}
		fprintf(fout, "%c", nr_to_RB(matrix[i][M1]));
		fprintf(fout, "\n");
	}
	fprintf(fout, "\n");
}

/*void printTree(FILE *fout, mw_ITree *tree, int tabs_count)
{
	if(tree == NULL)
		return;
	mw_ITree *p;
	for(p = tree->left; p != NULL; p = p->right) {
		if(p->value == INF || p->value == -INF)
			//fprintf(fout, "inf | ");
			continue;
		printTabs(fout, tabs_count);
		//TODO: JUST THE p->value!!!
		fprintf(fout, "%d\n", p->value);
		/*
		if(p->alpha == -INF)
			fprintf(fout, "-inf | ");
		else
			fprintf(fout, "%d | ", p->alpha);
		if(p->beta == INF)
			fprintf(fout, "inf\n");
		else
			fprintf(fout, "%d\n", p->beta);

		printTree(fout, p, tabs_count + 1);
	}
	free(p);
}*/

void printTree(FILE *fout, mw_ITree *tree, int tabs_count)
{
	if(tree == NULL)
		return;
	mw_ITree *p;
	for(p = tree->left; p != NULL; p = p->right) {
		if(p->value == INF || p->value == -INF)
			continue;
		printTabs(fout, tabs_count);
		fprintf(fout, "%d\n", p->value);
		printTree(fout, p, tabs_count + 1);
	}
	free(p);
}

bool is04(int x)
{
	if(x == 0 || x == 4)
		return 1;
	return 0;
}

bool isEndOfTheGame(int N, int M, int i, int j, char mtrx[20][20])
{
	int H1, H2, H3, H4;
	int V1, V2, V3, V4;
	int R1, R2, R3, R4;
	int L1, L2, L3, L4;
	H1 = H2 = H3 = H4 = V1 = V2 = V3 = V4 = cINF;
	R1 = R2 = R3 = R4 = L1 = L2 = L3 = L4 = cINF;
	//Calculul sumelor pe orizontala
	if(j < M - 3)
		H1 = mtrx[i][j] + mtrx[i][j + 1] + mtrx[i][j + 2] + mtrx[i][j + 3];
	if(0 < j && j < M - 2)
		H2 = mtrx[i][j - 1] + mtrx[i][j] + mtrx[i][j + 1] + mtrx[i][j + 2];
	if(1 < j && j < M - 1)
		H3 = mtrx[i][j - 2] + mtrx[i][j - 1] + mtrx[i][j] + mtrx[i][j + 1];
	if(2 < j)
		H4 = mtrx[i][j - 3] + mtrx[i][j - 2] + mtrx[i][j - 1] + mtrx[i][j];
	//Calculul sumelor pe verticala
	if(i < N - 3)
		V1 = mtrx[i][j] + mtrx[i + 1][j] + mtrx[i + 2][j] + mtrx[i + 3][j];
	if(0 < i && i < N - 2)
		V2 = mtrx[i - 1][j] + mtrx[i][j] + mtrx[i + 1][j] + mtrx[i + 2][j];
	if(1 < i && i < N - 1)
		V3 = mtrx[i - 2][j] + mtrx[i - 1][j] + mtrx[i][j] + mtrx[i + 1][j];
	if(2 < i)
		V4 = mtrx[i - 3][j] + mtrx[i - 2][j] + mtrx[i - 1][j] + mtrx[i][j];
	//Calculul sumelor pe diagonala paralela cu diagonala principala
	if(i < N - 3 && j < M - 3)
		R1 = mtrx[i][j] + mtrx[i + 1][j + 1] + mtrx[i + 2][j + 2] + mtrx[i + 3][j + 3];
	if(0 < i && i < N - 2 && 0 < j && j < M - 2)
		R2 = mtrx[i - 1][j - 1] + mtrx[i][j] + mtrx[i + 1][j + 1] + mtrx[i + 2][j + 2];
	if(1 < i && i < N - 1 && 0 < j && j < M - 1)
		R3 = mtrx[i - 2][j - 2] + mtrx[i - 1][j - 1] + mtrx[i][j] + mtrx[i + 1][j + 1];
	if(2 < i && 2 < j)
		R4 = mtrx[i - 3][j - 3] + mtrx[i - 2][j - 2] + mtrx[i - 1][j - 1] + mtrx[i][j];
	//Calculul sumelor pe diagonala parelala cu diagonala secundara
	if(i < N - 3 && 2 < j)
		L1 = mtrx[i + 3][j - 3] + mtrx[i + 2][j - 2] + mtrx[i + 1][j - 1] + mtrx[i][j];
	if(0 < i && i < N - 2 && 1 < j && j < M - 1)
		L2 = mtrx[i + 2][j - 2] + mtrx[i + 1][j - 1] + mtrx[i][j] + mtrx[i - 1][j + 1];
	if(1 < i && i < N - 1 && 0 < j && j < M - 2)
		L3 = mtrx[i + 1][j - 1] + mtrx[i][j] + mtrx[i - 1][j + 1] + mtrx[i - 2][j + 2];
	if(2 < i && j < M - 3)
		L4 = mtrx[i][j] + mtrx[i - 1][j + 1] + mtrx[i - 2][j + 2] + mtrx[i - 3][j + 3];
	//Verificarea sumelor
	if(is04(H1) || is04(H2) || is04(H3) || is04(H4) ||
	        is04(V1) || is04(V2) || is04(V3) || is04(V4) ||
	        is04(R1) || is04(R2) || is04(R3) || is04(R4) ||
	        is04(L1) || is04(L2) || is04(L3) || is04(L4))
		return 1;
	//Daca nu se termina prin castig jocul,
	// se termina cand nu mai exista spatii.
	for(i = 0; i < N; ++i)
		for(j = 0; j < M; ++j)
			if(mtrx[i][j] == 8)//cod personal pentru '-'
				return 0;
	return 1;
}

void place_chip(FILE *fout, int N, int M, mw_MTree *tree, char chip, int depth)
{
	int i, j;
	for(j = 0 ; j < M; ++j) {//TODO: maybe? modify swap fors
		for(i = N - 1; i >= 0; --i) {
			if(tree->matrix[i][j] == 8) {//cod personal pentru '-'
				mw_MTree *p = malloc(sizeof(mw_MTree));
				int ki, kj;
				for(ki = 0; ki < N; ++ki) {
					for(kj = 0; kj < M; ++kj)
						p->matrix[ki][kj] = tree->matrix[ki][kj];
				}
				p->matrix[i][j] = chip;
				printMatrix(fout, N, M, p->matrix, depth + 1);
				if(!isEndOfTheGame(N, M, i, j, p->matrix)) {
					insert_MTree(tree, p);
					place_chip(fout, N, M, p, chip ^ 1, depth + 1);
					//jetonul urmator pus va fi pus (chip xor 1)
				}
				free(p);
				break;
			}
		}
	}
}

int maxValue(mw_ITree *tree)
{
	//nu ar trebui ca tree sa fie NULL
	//tree are cel putin un fiu, caci altfel nu se apela functia
	//calculeaza maximul valorii copiilor lui tree
	mw_ITree *p;
	int maxx = -INF;
	for(p = tree->left; p != NULL; p = p->right) {
		if(p->value == INF)
			p->value = Minimax(p, 0);
		if(p->value > maxx)
			maxx = p->value;
	}
	return maxx;
}

int minValue(mw_ITree *tree)
{
	//nu ar trebui ca tree sa fie NULL
	//tree are cel putin un fiu, caci altfel nu se apela functia
	//calculeaza minimul valorii copiilor lui tree
	mw_ITree *p;
	int minn = INF;
	for(p = tree->left; p != NULL; p = p->right) {
		if(p->value == INF)
			p->value = Minimax(p, 1);
		if(p->value < minn)
			minn = p->value;
	}
	return minn;
}

int Minimax(mw_ITree *tree, bool mM)
{
	//mM: 0 - tura lui Min, 1 - tura lui Max
	if(tree == NULL)
		return 0;
	//daca nu mai are copii, atunci el e o frunza
	//  si valoarea lui maxima/minima e tree->value
	if(tree->left == NULL)//nu are copii
		return tree->value;
	if(mM)
		return maxValue(tree);
	else
		return minValue(tree);
}

void Task1(FILE *fin, FILE *fout)
{
	int N, M, i, j;
	char RB, chip;
	fscanf(fin, "%d %d %c\n", &N, &M, &RB);
	chip = RB_to_nr(RB);
	mw_MTree *tree = malloc(sizeof(mw_MTree));
	tree->left = NULL;
	tree->right = NULL;
	for(i = 0; i < N; ++i) {
		for(j = 0; j < M; ++j) {
			char RB;
			fscanf(fin, "%c ", &(RB));
			tree->matrix[i][j] = RB_to_nr(RB);
		}
	}
	printMatrix(fout, N, M, tree->matrix, 0);
	place_chip(fout, N, M, tree, chip, 0);
	free(tree);
}

void insert_ITree(mw_ITree *parent, mw_ITree *child)
{
	child->left = NULL; //copilul nu are alti copii... e prea mic
	child->right = NULL;//copilul inca nu are si frati mai mici
	child->parent = parent;
	if(parent->left == NULL) {
		parent->left = child;
		return;
	}
	mw_ITree *p, *p_next;
	for(p = parent->left; p->right != NULL;) {
		p_next = p->right;
		p = p_next;
	}
	p->right = child;
}

void insert_ITQueue(mw_ITQueue **parent, mw_ITQueue *child)
{
	child->next = NULL;
	if((*parent) == NULL) {
		(*parent) = child;
		return;
	}
	mw_ITQueue *p, *p_next;
	for(p = (*parent); p->next != NULL;) {
		p_next = p->next;
		p = p_next;
	}
	p->next = child;
}

mw_ITree *pop(mw_ITQueue **Q)
{
	if((*Q) == NULL)
		return NULL;
	mw_ITree *tree;
	mw_ITQueue *temp;
	tree = (*Q)->tree;
	temp = (*Q);
	(*Q) = (*Q)->next;
	free(temp);
	return tree;
}

void pop_all(mw_ITQueue **dest, mw_ITQueue **src)
{
	while((*src)) {
		mw_ITQueue *p = malloc(sizeof(mw_ITQueue));
		mw_ITree *tree;
		mw_ITQueue *temp;
		p->next = NULL;
		tree = (*src)->tree;
		temp = (*src);
		(*src) = (*src)->next;
		free(temp);
		p->tree = tree;
		insert_ITQueue(&(*dest), p);
	}
}

void Task2(FILE *fin, FILE *fout)
{
	//TODO: maybe? set alpha, beta = 0, just in case
	mw_ITree *root = malloc(sizeof(mw_ITree));
	mw_ITree *crt;
	mw_ITQueue *old_level = malloc(sizeof(mw_ITQueue));
	mw_ITQueue *crt_level;
	int L, i, j, k, sum, nr_CrtLvl_Children;
	fscanf(fin, "%d\n(%d)\n", &L, &(nr_CrtLvl_Children));
	root->nrChild = nr_CrtLvl_Children;
	root->value = INF;
	root->left = NULL;
	root->right = NULL;
	old_level->tree = root;
	old_level->next = NULL;
	crt_level = NULL;
	for(i = 1; i < L; ++i) {
		sum = 0;
		k = 0;
		crt = pop(&old_level);
		for(j = 0; j < nr_CrtLvl_Children; ++j) {
			int x;
			char prt, prt2;
			mw_ITree *nodeT = malloc(sizeof(mw_ITree));
			mw_ITQueue *nodeQ = malloc(sizeof(mw_ITQueue));
			nodeT->left = NULL;
			nodeT->right = NULL;
			nodeQ->next = NULL;
			nodeQ->tree = NULL;
			fscanf(fin, "%c%d%c ", &prt, &x, &prt2);
			if(prt == '(') {
				sum += x;
				nodeT->value = INF;
				nodeT->nrChild = x;
				nodeQ->tree = nodeT;
				insert_ITree(crt, nodeT);
				insert_ITQueue(&crt_level, nodeQ);
				//free(nodeQ);
			}
			if(prt == '[') {
				nodeT->value = x;
				nodeT->nrChild = 0;
				nodeQ->tree = nodeT;
				insert_ITree(crt, nodeT);
				free(nodeQ);
			}
			if(++k == crt->nrChild) {
				k = 0;
				crt = pop(&old_level);
			}
		}
		nr_CrtLvl_Children = sum;
		//old_level is freed and NULL now
		pop_all(&old_level, &crt_level);
		//old_level = crt_level
		//crt_level is freed and NULL now
	}
	root->value = Minimax(root, 1);
	fprintf(fout, "%d\n", root->value);
	printTree(fout, root, 1);
	free(crt);
	free(crt_level);
	freeIT(root);
}

bool full_child(mw_ITree *node)
{
	int count = 0;
	mw_ITree *p;
	for(p = node->left; p != NULL; p = p->right)
		if(p->value != INF)
			++count;
		else
			break;
	if(count == node->nrChild)
		return true;
	return false;
}

void AB_copy(mw_ITree *q, mw_ITree *node)
{
	// q = node, just for alpha, beta
	q->alpha = node->alpha;
	q->beta = node->beta;
}

void AB_copy_leftside(mw_ITree *q, mw_ITree *node)
{
	if(q->left == NULL)
		return;
	AB_copy(q, node);
	AB_copy_leftside(q->left, node);
}
/*
void AB_copy_downside(mw_ITree *q, mw_ITree *node)
{
	if(q->left == NULL)
		return;
    if(q->alpha != -INF || q->beta != INF)
        return;
	AB_copy(q, node);
	mw_ITree *p;
    for(p = node->left; p != NULL; p = p->right)
        AB_copy_downside(q->left, node);
}*/

void AB_pruning(mw_ITree *node, bool mM)
{
	if(node == NULL)
		return;
	mw_ITree *q;
	for(q = node->left; q != NULL; q = q->right) {
		if(node->alpha >= node->beta) {
			q->value = INF;
			continue;
		}
		//can be better
		if(q->left != NULL && q != node->left) {
			AB_copy(q, node);
			AB_copy_leftside(q, node);
		}
		if(q->value == INF || q->value == -INF)
			AB_pruning(q, mM ^ 1);
		if(mM) {
			if(q->alpha > node->alpha)
				node->alpha = q->alpha;
			if(q->beta != INF && q->beta > node->alpha)
				node->alpha = q->beta;
			if(q->value > node->value)
				node->value = q->value;
		} else {
			if(q->alpha != -INF && q->alpha < node->beta)
				node->beta = q->alpha;
			if(q->beta < node->beta)
				node->beta = q->beta;
			if(q->value < node->value)
				node->value = q->value;
		}
	}
	//fprintf(stdout, "%d | %d | %d\n", root->value, root->alpha, root->beta);
	//printTree(stdout, root, 1);
	//printf("\n\n");
}

void Task3(FILE *fin, FILE *fout)
{
	mw_ITree *root = malloc(sizeof(mw_ITree));
	mw_ITree *crt;
	mw_ITQueue *old_level = malloc(sizeof(mw_ITQueue));
	mw_ITQueue *crt_level;
	int L, i, j, k, sum, nr_CrtLvl_Children;
	fscanf(fin, "%d\n(%d)\n", &L, &(nr_CrtLvl_Children));
	root->nrChild = nr_CrtLvl_Children;
	root->value = -INF;
	root->alpha = -INF;
	root->beta = INF;
	root->left = NULL;
	root->right = NULL;
	old_level->tree = root;
	old_level->next = NULL;
	crt_level = NULL;
	for(i = 1; i < L; ++i) {
		sum = 0;
		k = 0;
		crt = pop(&old_level);
		for(j = 0; j < nr_CrtLvl_Children; ++j) {
			int x;
			char prt, prt2;
			mw_ITree *nodeT = malloc(sizeof(mw_ITree));
			mw_ITQueue *nodeQ = malloc(sizeof(mw_ITQueue));
			nodeT->left = NULL;
			nodeT->right = NULL;
			nodeQ->next = NULL;
			nodeQ->tree = NULL;
			fscanf(fin, "%c%d%c ", &prt, &x, &prt2);
			if(prt == '(') {
				sum += x;
				nodeT->alpha = -INF;
				nodeT->beta = INF;
				if(i & 1) //impar
					nodeT->value = INF;
				else    //par
					nodeT->value = -INF;
				nodeT->nrChild = x;
				nodeQ->tree = nodeT;
				insert_ITree(crt, nodeT);
				insert_ITQueue(&crt_level, nodeQ);
				//free(nodeQ);
			}
			if(prt == '[') {
				nodeT->value = x;
				nodeT->nrChild = 0;
				nodeT->alpha = x;
				nodeT->beta = x;
				nodeQ->tree = nodeT;
				insert_ITree(crt, nodeT);
				free(nodeQ);
			}
			if(++k == crt->nrChild) {
				k = 0;
				crt = pop(&old_level);
			}
		}
		nr_CrtLvl_Children = sum;
		//old_level is freed and NULL now
		pop_all(&old_level, &crt_level);
		//old_level = crt_level
		//crt_level is freed and NULL now
	}
	//fprintf(fout, "%d\n", root->value);
	// printTree(fout, root, 1);
	//
	AB_pruning(root, 1);
	//
	//fprintf(fout, "%d | %d | %d\n", root->value, root->alpha, root->beta);
	fprintf(fout, "%d\n", root->value);
	printTree(fout, root, 1);
	free(crt);
	free(crt_level);
	freeIT(root);
}

void TaskBonus()
{
}