// tris.cpp : definisce il punto di ingresso dell'applicazione console.
//


#define _WIN32_WINNT 0x0501
#include <windows.h>
#include <wincon.h> //g++ tris.cpp -o tris.exe -lkernel32 -lgdi32

#include <iostream>
#include <cmath>
using namespace std;
#include <conio.h>
#include <windows.h> 
#include <climits>
#pragma comment(lib,"kernel32.lib")
CONSOLE_SCREEN_BUFFER_INFO csbiInfo; 
int Colors = FOREGROUND_GREEN|BACKGROUND_BLUE|FOREGROUND_INTENSITY;

const int NR=3;
const int NC=NR;
int _QM[NR][NC]={
	{8 ,1, 6},
	{3, 5 ,7},
	{4, 9, 2}};
int QM[NR][NC];
void DumpMatrix(int M[NR][NC])
{
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
			cout << M[r][c] << " ";
		cout << endl;
	}
	cout << endl;
}

int D2toD1(int r,int c,int NC)
{
	return (r)*NC + c;
}

void D1toD2(int k, int &r, int &c, int NC)
{
	r = k / NC;
	c = k % NC;
}

int GetNextPlayer(int player)
{
	return (player+1) %2;
}

bool isFree(int v)
{
	return v < 10;
}
bool isFree(int T[NR][NC],int r,int c)
{
	return T[r][c] < 10;
}

bool isValid(int T[NR][NC],int r, int c)
{
	bool bRet=false;
	bRet=((r>=0 && r < NC) && (c>=0 && c<NC));
	return bRet && isFree(T,r,c);
}

char Decode(int r,int c)
{
	int v=QM[r][c];
	if(v >= 100)
		return 'O';
	else if (v>=10)
		return 'X';
	else
		return 0x30 + D2toD1(r,c,NC)+1;
}

int Encode(int player)
{
	return pow(10,player+1);
}

void printMap2DExt()
{
	const int Cross=197;
	const int ULCorner=218;
	const int URCorner=191;
	const int DLCorner=192;
	const int DRCorner=217;
	const int Vert=179;
	const int Horz=196;//45
	const int LCross=195;
	const int RCross=180;
	const int UCross=194;
	const int DCross=193;

	int cellWidth=3;
	int cellHeight=3;
	cellWidth+=2;
	cellHeight+=2;
	char ch=0;
	for(int r=0; r < NR; r++)
	{
		for(int i=0; i < cellHeight ; i++)
		{
			for(int c=0; c < NC; c++)
				for(int j=0; j < cellWidth; j++)
				{
					if(!(i==0 && r>0))
					{
					ch=' ';
					if((i==cellHeight/2) && (j==cellWidth/2))
						ch = Decode( r,c);
					if(i==0 || (i == cellHeight-1))
						ch=Horz;
					if(i>0 && i < (cellHeight-1) && (j==0 || j== (cellHeight-1)))
						ch=Vert;
					if(i==0 && j==0 && r==0 && c==0)
						ch=ULCorner;
					if(i==0 && (j==cellWidth-1) && r==0 && c==NC-1)
						ch=URCorner;
					if((i==cellHeight-1) && j==0 && r==NR-1 && c==0)
						ch=DLCorner;
					if((i==cellHeight-1) && j==cellWidth-1 && r==NR-1 && c==NC-1)
						ch=DRCorner;

					if(i==cellHeight-1)
					{
						if(j==0 && c==0 && r<NR-1)
							ch = LCross;
						if(j==cellWidth-1)
						{
							if(c>=0 && c < NC-1 && r<NR-1)
								ch=Cross;
							if(c == NC-1 && r<NR-1)
								ch = RCross;
							if(c>=0 && c < NC-1 && r == NR-1)
								ch=DCross;

						}
					}
					if(i==0)
						if(j==cellWidth-1)
							if(r==0 && c>=0 && c<NC-1)
								ch=UCross;

					if((j==0 && c>0) || (i==0 && r>0))
						ch=0;
					if (ch !=0)
						cout << ch;
					ch=0;
					}}
				if(!(i==0 && r>0))
					cout << endl;
				
		}
	}
	cout << endl<<endl;
}

void printMap2D()
{
	int cellWidth=3;
	int cellHeight=3;
	cellWidth+=2;
	cellHeight+=1;
	char ch='-';
	for(int r=0; r < NR; r++)
	{
		for(int i=0; i < cellHeight ; i++)
		{
			for(int c=0; c < NC; c++)
				for(int j=0; j < cellWidth; j++)
				{
					if((i==0))
					{
						ch = ((j==0 )|| (j==cellWidth-1) ?'+':'-');
						if(('+' == ch) && c>0 && (j==0))
							cout<<"\b";
					}
					else
					{
						ch = (j==0 || j==cellWidth-1?'|':' ');
						if(('|' == ch) && c>0 && (j==0))
							cout<<"\b";
						if((i==cellHeight/2) && (j==cellWidth/2))
							ch = Decode( r,c);
					}
					cout << ch;
				}
				cout << endl;
		}
	}
	for(int c=0; c < NC; c++)
	{
		for(int j=0; j < cellWidth; j++)
		{			 ch = ((j==0 )|| (j==cellWidth-1) ?'+':'-');
		if(('+' == ch) && c>0 && (j==0))
			cout<<"\b";
		cout << ch;
		}	
	}
	cout << endl<<endl;
}

void printMapRaw()
{
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
		{
			int v=QM[r][c];
			if(v >= 100)
				cout << 'O';
			else if (v>=10)
				cout << 'X';
			else
				cout << D2toD1(r,c,NC)+1;
		}
		cout << endl;
	}
}
void printMap(bool bColor=false)
{
	system("CLS");

	if (bColor)
	{
		GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbiInfo);
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),Colors);//|COMMON_LVB_REVERSE_VIDEO);
	}
	printMap2DExt();

	if (bColor)
	{
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), csbiInfo.wAttributes);
	}
	return;

}


bool updateMap(int n,int player)
{
	n--;
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
		{
			int tr,tc;

			D1toD2(n,tr,tc,NC);
			if((tr==r && tc == c) && isFree(QM,tr,tc))
			{
				QM[r][c] *= Encode(player);
				return true;
			}
		}
	}
	return false;
}

int TotWin(int T[NR][NC],int player)
{
	int Tot=0;
	int sum=0;
	int kWin = 0;
	for(int r=0; r < NR; r++)
	{sum=0;
	for(int c=0; c < NC; c++)
	{
		if(T[r][c]>=Encode(player) && T[r][c]< Encode(player+1))
			sum+=T[r][c];
		if(sum==15*Encode(player))
		{kWin++;}
	}
	}
	for(int c=0; c < NC; c++)
	{sum=0;

	for(int r=0; r < NR; r++)
	{
		if(T[r][c]>=Encode(player) && T[r][c]< Encode(player+1))
			sum+=T[r][c];
		if(sum==15*Encode(player))
		{kWin++;}
	}
	}
	sum=0;
	for(int r=0; r < NR; r++)
	{
		int c=r;
		{
			if(T[r][c]>=pow(10,player+1) && T[r][c]< pow(10,player+1+1))
				sum+=T[r][c];
			if(sum==15*Encode(player))
			{kWin++;}
		}
	}
	sum=0;
	for(int r=0; r < NR; r++)
	{
		int c=NC-r-1;
		{
			if(T[r][c]>=Encode(player) && T[r][c]< Encode(player+1))
				sum+=T[r][c];
			if(sum==15*Encode(player))
			{kWin++;}
		}
	}
	return kWin; 
}
void copy(int TO[NR][NC],int FROM[NR][NC])
{
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
		{
			TO[r][c]=FROM[r][c];
		}
	}
}

int GetNumWin(int T[NR][NC],int player)
{
	return TotWin(T,player);
}

int GetMin(int S[NR][NC],int player)
{
	int T[NR][NC];
	copy(T,S);

	int ret=0;
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
		{
			if(isFree(T[r][c]))
			{
				T[r][c]*= Encode(player);
			}
		}
	}
	ret=GetNumWin(T,player);
	return ret;
}

bool hold(int T[NR][NC],int r, int c, int player)
{
	if (isFree(T[r][c]))
	{
		T[r][c]*= Encode(player);
		return true;
	}
	return false;
}
void setFree(int T[NR][NC],int r, int c)
{
	T[r][c]= QM[r][c];
}

void Solve(int X[NR][NC],int player,int &RBest,int &CBest)
{
	int T[NR][NC];
	int Z[NR][NC];
	RBest=-1;CBest=-1;
	copy(T,X);
	int nextPlayer=GetNextPlayer(player);
	int emin=INT_MAX;
	int emax=INT_MIN;
	int p1=0,p0=0;
	for(int r=0; r < NR; r++)
	{
		for(int c=0; c < NC; c++)
		{
			if(isFree(T[r][c]))
			{
				hold(T,r,c,player);
				copy(Z,T);
				for(int nr=0; nr < NR; nr++)
					for(int nc=0; nc < NC; nc++)
						if(isFree(T[nr][nc]))
						{
							hold(Z,nr,nc,nextPlayer);
							p1=GetMin(Z,nextPlayer);
							p0=GetMin(Z,player);
							emin=min(emin,p0-p1);
							setFree(Z,nr,nc);
						}
						setFree(T,r,c);
						if(emax<emin)
						{
							RBest=r;CBest=c;
						}
						emax=max(emax,emin);emin=INT_MAX;}
		}
	}
}


bool HasFree(int T[NR][NC])
{
	for(int r=0; r < NR; r++)
		for(int c=0; c < NC; c++)
			if(isFree(T[r][c]))
				return true;
	return false;
}

int winner=-1;
int player = 0;
int Human=0;

void Init()
{
	copy(QM,_QM);
	player=0;
	Human= ! Human;
	printMap();
}
void test()
{
			int myr=-1;
			int myc=-1;

			Solve(QM,player,myr,myc);
			cout << myr << "        " << myc << endl;
}
char PlayerToChar(int player)
{
	return (player==0?'X':'O');
}

int main()
{   
	bool bContinue=true;
	int x,k=0;
	char ch;

	Init();
	
	//test();
	
	while(bContinue)
	{
		winner=-1;
		cout << "Player " << (player==0?'X':'O') << ' ';
		if(Human==player)
		{
			int v;
			int tr=-1,tc=-1;
			do{
				ch = getch();
				if(0x1B == ch)
					goto quit;
				else
				{
					v=atoi((const char *)&ch);
					D1toD2(v-1,tr,tc,NC);
				}
			}while (!((v>0 && v < 10) && isValid(QM,tr,tc))); 
			if (isValid(QM,tr,tc))
			{
				if(updateMap(v,player))
					k++;
			}
		}
		else
		{
			int myr=-1;
			int myc=-1;
			Solve(QM,player,myr,myc);
			if(isValid(QM,myr,myc))
				if (isFree(QM,myr,myc))
					hold(QM,myr,myc,player);
		}
		printMap();
		if (TotWin(QM,player)>0)
		{
			winner = player;
			cout << "Player " << PlayerToChar(winner) << " WIN!!!" << endl;
			ch=getch();
			if(0x1B == ch)
				goto quit;
			Init();
		}
		else
		{
			if (TotWin(QM,GetNextPlayer(player))>0)
			{
				winner = GetNextPlayer(player);//player;
				cout << "Player " << PlayerToChar(winner) << " WIN!!!" << endl;
				ch=getch();
				if(0x1B == ch)
					goto quit;
				Init();

			}
		}
		if(winner <0)
		{
			if(HasFree(QM)==false)
			{
				cout << "NO Winner" <<endl;
				ch=getch();
				if(0x1B == ch)
					goto quit;
				Init();
			}
			else
				player=GetNextPlayer(player);

		}

	}

quit:
	cout << endl;
	system("PAUSE");
	return 0;
}