// MyTronBot.cc
//
// This is the code file that you will modify in order to create your entry.

#include "Map.h"
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <stdio.h>
#include <stdarg.h>

#define INFINI 9999999

int dir[][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
std::string convert[4] = {"NORTH", "EAST", "SOUTH", "WEST"};

struct Sommet {
	int distance;
	int distanceApprox;
	int directionPrec;
	int x,y;
};

struct CoordPcc {
	int x,y;
	CoordPcc* next;
};

struct CoordArtic {
	int x,y;
	int aire;
	CoordArtic* next;
};

struct infosartic {
   int dfsnum;
   int dfslevel;
   int low;
   int numChildren;
	int marquage;
};


#ifndef DEBUG
		void myprintf(const char *format, ...) {

		}
#else
		void myprintf(const char *format, ...) {
		  va_list pa;
		  int n;
		  char *s;
		  int c;
		  float f;
		  
		  va_start(pa, format);
		  while (*format != '\0') {
			 if ( *format == '%' ) {
				switch (*++format) {
				  case '%' : putchar('%'); break;
				  case 'c' : /* affichage d'un caractère */ 
								 c = va_arg(pa, int);
								 fprintf(stderr, "%c", c);
								 break;
				  case 'd' : /* affichage d'un entier */ 
								 n = va_arg(pa, int);
								 fprintf(stderr, "%d", n); 
								 break;
				  case 'f' : /* affichage d'un float */ 
								 f = va_arg(pa, double);    /* !!!!! */
								 fprintf(stderr, "%f", f); 
								 break;
				  case 's' : /* affichage d'une chaîne */ 
								 s = va_arg(pa, char *);
								 fprintf(stderr, "%s", s);
								 break;
				  case 'x' : 
								 n = va_arg(pa, int);
								 fprintf(stderr, "%x", n);
								 break;
				} /* end switch */
			 }
			 else 
				fprintf(stderr, "%c", *format);
			 format++;
		  }   
		  va_end(pa);
		}
#endif

class myMap {
	public:

		myMap(const Map& map) {
			is_wall =
				std::vector<std::vector<char> >(map.Width(),
				    std::vector<char>(map.Height(), false));

			map_width = map.Width();
			map_height = map.Height();
			memeZone = true;
			pcc_list = NULL;
			cv_list = NULL;
			for (int d = 0; d < 4; d++) {
				count_dir[d] = 0;
			}

			for (int x = 0; x < map.Width(); x++) {
				for (int y = 0; y < map.Height(); y++) {
					is_wall[x][y] = map.IsWall(x, y);
				}
			}
		}

		myMap(const myMap& map) {
			x = map.x;
			y = map.y;
			opp_x = map.opp_x;
			opp_y = map.opp_y;
			map_width = map.map_width;
			map_height = map.map_height;
			memeZone = map.memeZone;
			pcc_list = map.pcc_list;
			cv_list = cv_list;
			for (int d = 0; d < 4; d++) {
				count_dir[d] = map.count_dir[d];
			}
			is_wall =
				 std::vector<std::vector<char> >(map.map_width,
				    std::vector<char>(map.map_height, false));
			for (int y = 0; y < map_height; y++) {
				for (int x = 0; x < map_width; x++) {
					is_wall[x][y] = map.is_wall[x][y];
				}
			}
		}

		int min_count_dir() {
			int min = count_dir[0];
			for (int d=1; d < 4; d++) {
				if (count_dir[d] < min) {
					min = count_dir[d];
				}
			}
			return min;
		}

		int max_count_dir() {
			int max = 0;
			for (int d=0; d < 4; d++) {
				if (count_dir[d] > max) {
					max = count_dir[d];
				}
			}
			return max;
		}

		void init_cv() {
			CoordArtic *aux;
			CoordArtic *cur = cv_list;
			while (cur != NULL) {
				aux = cur->next;
				delete cur;
				cur = aux;
			}
			cv_list = NULL;
		}

		struct CoordArtic * is_cv(int x, int y) {
			CoordArtic *cur = cv_list;
			while (cur != NULL) {
				if (cur->x == x && cur->y == y) {
					return cur;
				}
				cur = cur->next;
			}
			return cur;
		}


		void init_pcc() {
			CoordPcc *aux;
			CoordPcc *cur = pcc_list;
			while (cur != NULL) {
				aux = cur->next;
				delete cur;
				cur = aux;
			}
			pcc_list = NULL;

			for (int d=0; d < 4; d++) {
				count_dir[d] = 0;
			}
		}

		int distanceOpp(int *d) {
			std::queue<Sommet> Queue;
			std::vector<std::vector<int> > marquagepcc =
				 std::vector<std::vector<int> >(map_width,
				    std::vector<int>(map_height, -1));

			Sommet depart;
			depart.distance = 0;
			depart.distanceApprox = 0;
			depart.directionPrec = 5;
			depart.x = opp_x;
			depart.y = opp_y;

			Queue.push(depart);
			while(!Queue.empty()) {
				Sommet courant = Queue.front();
				Queue.pop();

				if (marquagepcc[courant.x][courant.y] != -1) {
					continue;
				}
				marquagepcc[courant.x][courant.y] = courant.directionPrec;

				if (courant.x == x && courant.y == y) {
					*d = courant.directionPrec;

					// Marque le chemin !
					init_pcc();

					int dprec = courant.directionPrec;
					pcc_list = new CoordPcc;
					pcc_list->x = x;
					pcc_list->y = y;
					pcc_list->next = NULL;
					
					while (dprec >= 0 && dprec < 4) {
						count_dir[dprec]++;
						CoordPcc *element = new CoordPcc;
						element->x = pcc_list->x + dir[dprec][0];
						element->y = pcc_list->y + dir[dprec][1];
						element->next = pcc_list;
						pcc_list = element;	
						dprec = marquagepcc[pcc_list->x][pcc_list->y];
					}

					return courant.distance;
				}

				for (int i=0; i < 4; i++) {
					int suiv_x = courant.x+dir[i][0];
					int suiv_y = courant.y+dir[i][1];
					if ((!is_wall[suiv_x][suiv_y] || (suiv_x == x && suiv_y == y))
							&& marquagepcc[suiv_x][suiv_y] == -1) {
						Sommet suivant;
						suivant.distance = courant.distance+1;
						suivant.distanceApprox = std::abs(x - suiv_x) + std::abs(y - suiv_y);
						suivant.directionPrec = (i + 2)%4;
						suivant.x = suiv_x;
						suivant.y = suiv_y;
						Queue.push(suivant);
					}
				}
			}
			*d = 0;
			return -1;
		}

		void Affiche() {
#ifdef DEBUG
			myprintf("[%d %d]\n", map_width, map_height);
			fflush(stderr);

			for (int y = 0; y < map_height; y++) {
				for (int x = 0; x < map_width; x++) {
					if (x == this->x && y == this->y) {
						myprintf("M");
					} else if (x == this->opp_x && y == this->opp_y) {
						myprintf("A");
					} else {
						bool pcc = false;
						CoordPcc *cur = pcc_list;
						while (cur != NULL) {
							if (cur->x == x && cur->y == y) {
								myprintf("+");
								pcc = true;
								break;
							}
							cur = cur->next;
						}
						if (pcc) {
							continue;
						}
						myprintf("%c", is_wall[x][y] + '0');
					}
				}
				myprintf("\n");
			}
			fflush(stderr);
#endif
		}

		bool IsWall(int x, int y) {
			if (x < 0 || x >= map_width || y < 0 || y >= map_height) {
				return true;
			}
			return is_wall[x][y] != 0;
		}

		void Marque(int x, int y) {
			is_wall[x][y] = 1;
		}

		void Marque(int x, int y, char val) {
			is_wall[x][y] = val;
		}

		void DeMarque(int x, int y) {
			is_wall[x][y] = 0;
		}

		void setX(int x) {
			this->x = x;
		}

		int getX() {
			return x;
		}

		void setY(int y) {
			this->y = y;
		}

		int getY() {
			return y;
		}

		void setOppX(int x) {
			this->opp_x = x;
		}

		int getOppX() {
			return opp_x;
		}

		void setOppY(int y) {
			this->opp_y = y;
		}

		int getOppY() {
			return opp_y;
		}

		int getWidth() {
			return map_width;
		}

		int getHeight() {
			return map_height;
		}

		bool calculMemeZone(int *score) {
			myMap *map2 = new myMap(*this);
			memeZone = false;
			*score = map2->scoreE(x, y, opp_x, opp_y, &memeZone);
			delete map2;

			return memeZone;
		}

		bool isMemeZone() {
			return memeZone;
		}

		char getMarque(int x, int y) {
			return is_wall[x][y];
		}

		void varanoi(int *score_mine, int *score_his, bool *flag_opp) {
			myMap *map2 = new myMap(*this);
			
			std::queue<Sommet> his;
			std::queue<Sommet> mine;

			Sommet sommet1;
			sommet1.x = x;
			sommet1.y = y;
			sommet1.distance = 0;

			map2->DeMarque(sommet1.x, sommet1.y);
			
			Sommet sommet2;
			sommet2.x = opp_x;
			sommet2.y = opp_y;
			sommet2.distance = 0;

			map2->DeMarque(sommet2.x, sommet2.y);

			mine.push(sommet1);
			his.push(sommet2);

			*score_mine = 0;
			*score_his = 0;
			int cur_dist = 0;
			while (!his.empty() || !mine.empty()) {
				if (!his.empty()) {
					Sommet curSommet = his.front();
					while (curSommet.distance == cur_dist) {
						his.pop();
						if (!map2->IsWall(curSommet.x, curSommet.y)) {
							(*score_his)++;
							map2->Marque(curSommet.x, curSommet.y, 2);
							for (int d = 0; d < 4; d++) {
								int x_suiv = curSommet.x + dir[d][0];
								int y_suiv = curSommet.y + dir[d][1];
								if (!map2->IsWall(x_suiv, y_suiv)) {
									Sommet nextSommet;
									nextSommet.x = x_suiv;
									nextSommet.y = y_suiv;
									nextSommet.distance = cur_dist+1;
									his.push(nextSommet);
								}
							}
						} else if (map2->getMarque(curSommet.x, curSommet.y) == 3) {
							(*score_mine)--;
							*flag_opp = true;
						}

						if (!his.empty()) {
							curSommet = his.front();
						} else {
							break;
						}
					}
				}

				if (!mine.empty()) {
					Sommet curSommet = mine.front();
					while (curSommet.distance == cur_dist) {
						mine.pop();
						if (!map2->IsWall(curSommet.x, curSommet.y)) {
							(*score_mine)++;
							map2->Marque(curSommet.x, curSommet.y, 3);
							for (int d = 0; d < 4; d++) {
								int x_suiv = curSommet.x + dir[d][0];
								int y_suiv = curSommet.y + dir[d][1];
								if (!map2->IsWall(x_suiv, y_suiv)) {
									Sommet nextSommet;
									nextSommet.x = x_suiv;
									nextSommet.y = y_suiv;
									nextSommet.distance = cur_dist+1;
									mine.push(nextSommet);
								}
							}
						} else if (map2->getMarque(curSommet.x, curSommet.y) == 2) {
							(*score_his)--;
							*flag_opp = true;
						}
						if (!mine.empty()) {
							curSommet = mine.front();
						} else {
							break;
						}
					}
				}

				cur_dist++;
			}
			delete map2;
		}

		void articpointdfs(int x, int y, std::vector<std::vector<struct infosartic> > * casesarticdfs) {
			int d;
			(*casesarticdfs)[x][y].dfsnum = dfscounter++;
			(*casesarticdfs)[x][y].low = (*casesarticdfs)[x][y].dfsnum;

			for (d = 0; d < 4; d++) {
				int x_ = x+dir[d][0];
				int y_ = y+dir[d][1];
				if (x_ < 0 || y_ < 0 || x_ >= map_width || y_ >= map_height || is_wall[x_][y_]) {
					continue;
				}

				if ((*casesarticdfs)[x_][y_].dfsnum == -1) {
					(*casesarticdfs)[x_][y_].dfslevel = (*casesarticdfs)[x][y].dfslevel+1;
					(*casesarticdfs)[x][y].numChildren++;
					articpointdfs(x_, y_, casesarticdfs);
					if ((*casesarticdfs)[x_][y_].low < (*casesarticdfs)[x][y].low) {
						(*casesarticdfs)[x][y].low = (*casesarticdfs)[x_][y_].low;
					}
					if ((*casesarticdfs)[x][y].dfsnum == 1) {
						if ((*casesarticdfs)[x][y].numChildren >= 2) {
							CoordArtic *nouveau = new CoordArtic;
							nouveau->x = x;
							nouveau->y = y;
							nouveau->aire = 0;
							nouveau->next = cv_list;
							cv_list = nouveau;
						}
					} else {
						if ((*casesarticdfs)[x_][y_].low >= (*casesarticdfs)[x][y].dfsnum) {
							CoordArtic *nouveau = new CoordArtic;
							nouveau->x = x;
							nouveau->y = y;
							nouveau->aire = 0;
							nouveau->next = cv_list;
							cv_list = nouveau;
						}
					}
				} else if ((*casesarticdfs)[x_][y_].dfslevel < (*casesarticdfs)[x][y].dfslevel - 1) {
					if ((*casesarticdfs)[x][y].low > (*casesarticdfs)[x_][y_].dfsnum) {
						(*casesarticdfs)[x][y].low = (*casesarticdfs)[x_][y_].dfsnum;
					}
				}
			}
		}

		int fillChamber(int x, int y, std::vector<std::vector<struct infosartic> > * casesarticdfs) {
			int s = 0;

			(*casesarticdfs)[x][y].marquage = 1;

			struct CoordArtic * c = is_cv(x, y);
			for (int d = 0; d < 4; d++) {
				int x_next = x + dir[d][0];
				int y_next = y + dir[d][1];
				if ((*casesarticdfs)[x_next][y_next].marquage == 0 && is_wall[x_next][y_next] == 0) {
					if (c == NULL) {
						s += fillChamber(x_next, y_next, casesarticdfs);
					} else {
						s = std::max(s, fillChamber(x_next, y_next, casesarticdfs));
					}
				}
			}
			return s + 1;
		}


		int computeCutVertices(int x, int y) {
			init_cv();
			dfscounter = 1;
			struct infosartic initialValue;
			initialValue.dfsnum = -1;
			initialValue.dfslevel = 0;
			initialValue.low = 0;
			initialValue.numChildren = 0;
			initialValue.marquage = 0;
			std::vector<std::vector<struct infosartic> > casesarticdfs = std::vector<std::vector<struct infosartic> >(map_width,
				    std::vector<struct infosartic>(map_height, initialValue));

			articpointdfs(x, y, &casesarticdfs);
			return fillChamber(x, y, &casesarticdfs);
		}

		int scoreE(int x, int y, int opp_x, int opp_y, bool *flag_opp, bool tracePcc=false) {
			int s = 1;

			if (tracePcc) {
				CoordPcc *cur = pcc_list;
				while (cur != NULL) {
					if (cur->x == x && cur->y == y) {
						return 0;
					}
					cur = cur->next;
				}
			}

			if (opp_x == x && opp_y == y) {
				*flag_opp = true;
				return 0;
			}

			is_wall[x][y] = 1;
			for (int i=0; i < 4; i++) {
				int x_suiv = x+dir[i][0];
				int y_suiv = y+dir[i][1];
				if (!(x_suiv < 0 || x_suiv >= map_width || y_suiv < 0 || y_suiv >= map_height) && (!is_wall[x_suiv][y_suiv] || (x_suiv == opp_x && y_suiv == opp_y))) {
					s += scoreE(x + dir[i][0], y + dir[i][1], opp_x, opp_y, flag_opp, tracePcc);
				}
			}

			return s;
		}

		int scoreMax(int x, int y, int opp_x, int opp_y, bool *flag_opp, bool tracePcc=false) {
			myMap *map2 = new myMap(*this);
			int max = 0;
			map2->Marque(x, y);
			for (int dd = 0; dd < 4; dd++) {
				if (!is_wall[x+dir[dd][0]][y+dir[dd][1]]) {
					bool opp_found = false;
					int score = map2->scoreE(x+dir[dd][0], y+dir[dd][1], opp_x, opp_y, &opp_found, tracePcc);
					if (score > max) {
						max = score;
						*flag_opp = opp_found;
					}
					max = std::max(max, score);
				}
			}
			delete map2;
			return max;
		}


	private:
	  std::vector<std::vector<char> > is_wall;
	  std::vector<std::vector<bool> > is_pcc;
	  int map_height;
	  int map_width;
	  int x,y,opp_x,opp_y;
	  bool memeZone;
	  CoordPcc *pcc_list;
	  CoordArtic *cv_list;
	  int count_dir[4];
	  int dfscounter;
};

int minimax(myMap *map, bool myTurn, int *direction, int depth, int depthMax, bool calculOpp, int alpha=-INFINI, int beta=INFINI) {
	if (depth == 0) {
		bool flag_opp = false;

		int s = 0, s2 = 0; 

		int d = 0;
		if (map->isMemeZone()) {
			map->varanoi(&s, &s2, &flag_opp);
			if (flag_opp) {
				int direction;
				d = map->distanceOpp(&direction);
				if (d > depthMax*2) {
					int d2 = map->max_count_dir();
					d *= -2;
					d -= d2;
				} else if (d >= depthMax) { // Si on est loin, c'est pas bien !
					int d2 = map->max_count_dir();
					d *= -1;
					d -= d2;
				} else {
					d = - map->max_count_dir();
				}
			} else {
				s = map->computeCutVertices(map->getX(), map->getY());
				s2 = map->computeCutVertices(map->getOppX(), map->getOppY());
				
				if ((s-s2) > (s+s2)/20) {
					d = 150;
				} else if (s-s2 > (s+s2)/40) {
					d = 50;
				} else if (s-s2 > -(s+s2)/40) {
					d = 0;
				} else if (s-s2 > -(s+s2)/20) {
					d = -50;
				} else {
					d = -150;
				}
			}
		} else {
			s = map->computeCutVertices(map->getX(), map->getY());
		}


		return (s-s2)*2 + d;
	} else {
		if (myTurn) {
			int x, y;
			x = map->getX();
			y = map->getY();

			int alpha = -INFINI + (depthMax - depth);
			bool valNotDef = true;

			map->Marque(x, y);
			for (int d = 0; d < 4; d++) {
				if (map->IsWall(x + dir[d][0], y + dir[d][1]) || (x+dir[d][0] == map->getOppX() && y+dir[d][1] == map->getOppY())) {
					continue;
				}

				map->setX(x + dir[d][0]);
				map->setY(y + dir[d][1]);

				int val;
				if (calculOpp) {
					val = minimax(map, !myTurn, direction, depth, depthMax, calculOpp, alpha, beta);
				} else {
					val = minimax(map, myTurn, direction, depth-1, depthMax, calculOpp, alpha, beta);
				}

				if (val >= alpha || valNotDef) {
					valNotDef = false;

					if (depth == depthMax) {
						bool better = true;
						if (val == alpha && d > 0) {
							int score1;
							int score2;
							score1 = minimax(map, false, NULL, 0, depthMax, calculOpp, alpha, beta);
							map->setX(x + dir[*direction][0]);
							map->setY(y + dir[*direction][1]);
							score2 = minimax(map, false, NULL, 0, depthMax, calculOpp, alpha, beta);
							better = (score1  > score2);
						}
						if (better) {
							*direction = d;
						}
					}
					alpha = val;
					if (val >= beta) {
						break;
					}
				}
			}
			map->setX(x);
			map->setY(y);

			map->DeMarque(x, y);

			return alpha;
		} else {

			int x, y;
			x = map->getOppX();
			y = map->getOppY();

			int beta = INFINI - (depthMax - depth);
			map->Marque(x, y);
			for (int d = 0; d < 4; d++) {
				int val;

				if (x+dir[d][0] == map->getX() && y+dir[d][1] == map->getY()) {
					val = -40 + (depthMax - depth);

					if (val < beta) {
						beta = val;

						if (val <= alpha) {
							break;
						}
					}
					continue;
				}
				
				if (map->IsWall(x + dir[d][0], y + dir[d][1])) {
					continue;
				}
				
				map->setOppX(x + dir[d][0]);
				map->setOppY(y + dir[d][1]);

				val = minimax(map, !myTurn, direction, depth-1, depthMax, calculOpp, alpha, beta);
				if (val < beta) {
					beta = val;

					if (val <= alpha) {
						break;
					}
				}
			}
			map->setOppX(x);
			map->setOppY(y);
			map->DeMarque(x, y);

			return beta;
		}

	}
}

int nbChemins(myMap *map, int x, int y, int depth) {
   int c = 0;

   if (depth == 0) {
      return 1;
   }
   if (depth > 0) {
      int d;
      for (d = 0; d < 4; d++) {
         int x_dest = x+dir[d][0];
         int y_dest = y+dir[d][1];

         if (!map->IsWall(x_dest, y_dest)) {
            map->Marque(x_dest, y_dest);
            c += nbChemins(map, x_dest, y_dest, depth-1);
            map->DeMarque(x_dest, y_dest);
         }
      }
   }  
   return c;
}

int calculDepth(myMap *map, bool calculOpp, int tailleZone) {
	int depth = 2;
	int n = 1;
	int borne;

	borne = std::max(200, 160000/tailleZone);
	borne *= calculOpp ? 1 : 3;
	while (n > 0 && n < borne && depth <= tailleZone) {
		depth++;
		n = nbChemins(map, map->getX(), map->getY(), depth);
		if (calculOpp) {
			n += nbChemins(map, map->getOppX(), map->getOppY(), depth);
		}
	}
	return depth-1;
}

std::string MakeMove(const Map& map) {
	static int count = 0;
	int d=0;
	count++;
	static myMap *map2 = new myMap(map);

	map2->setX(map.MyX());
	map2->setY(map.MyY());
	map2->setOppX(map.OpponentX());
	map2->setOppY(map.OpponentY());

	int nInitChoices = 0;
	for (int dd = 0; dd < 4; dd++) {
		if (!map2->IsWall(map2->getX()+dir[dd][0], map2->getY()+dir[dd][1])) {
			nInitChoices++;
			d = dd;
		}
	}
	if (nInitChoices > 1) {
		int tailleZone;
		bool memeZone = map2->calculMemeZone(&tailleZone);
		int depth = calculDepth(map2, memeZone, tailleZone) + (count == 0 ? 1 : 0) + (memeZone ? 0 : 1);

		int score = minimax(map2, true, &d, depth, depth, memeZone);
	}
				
	map2->Marque(map.MyX(), map.MyY());
	map2->Marque(map.OpponentX(), map.OpponentY());

	return convert[d];
}

// Ignore this function. It is just handling boring stuff for you, like
// communicating with the Tron tournament engine.
int main() {
  while (true) {
    Map map;
    Map::MakeMove(MakeMove(map));
  }
  return 0;
}