//
// http://en.wikipedia.org/wiki/F%C5%ABrinkazan
//
import util;
import game;

bool is_spacy(char c)
{
	return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
}

bool is_rocky(char c)
{
	return c=='*' || c=='@';
}

bool is_true_space(char c)
{
	return c==' ';
}

bool is_trampoline_source(char c)
{
	return 'A'<=c && c<='I';
}

bool is_rocklambda(char c)
{
	return is_rocky(c) || c=='\\';
}

Tuple!(string,int) death_move(in Game g)
{
	// TODO: S

	string death;
	int breath;
	int y = g.map.robot.y;
	int x = g.map.robot.x;
	int[5] dy_=[+1,-1,0,0,0];
	int[5] dx_=[0,0,-1,+1,0];
	char[] ds=['U','D','L','R','W'];
	for(int i=0; i<5; ++i)
	{
		bool after_move_death(int y, int x, char tr_tgt)
		{
			bool is_spacy_t(char c) {
				if(is_true_space(c) || c=='R' || c==tr_tgt)
					return true;
				return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
			}

			// check water
			if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level )
				return true;

			// check falling rock.
			int yy=y+1, xx=x;
			if( is_spacy_t(g.map[yy, xx]) )
			{
				if( is_rocky(g.map[yy+1,xx]) )
					return true;
				if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
					if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
						return false;
					return true;
				}
				if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
					if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
						return false;
					return true;
				}
			}
			return false;
		}

		int dy=dy_[i], dx=dx_[i];
		if( is_spacy(g.map[y+dy,x+dx]) || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
		{
			if( after_move_death(y+dy, x+dx, char.init) )
				death ~= ds[i];
			else if(ds[i] != 'W')
				breath ++;
		}
		else if( is_trampoline_source(g.map[y+dy,x+dx]) )
		{
			Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
			if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
				death ~= ds[i];
			else
				breath ++;
		}
		else
		{
			death ~= ds[i];
		}
	}

	return tuple(death, breath);
}

interface Solver
{
	// this(in Game g);
	char single_step();
	void force(char c);
}

class 不動如山 : Solver
{
	this(in Game g) {}
	char single_step() { return 'W'; }
	void force(char c) {}
}

class 徐如林 : Solver
{
	int wait_count = 0;
	int choke_count = 0;

	Game g;
	this(in Game g)
	{
		this.g = g.clone();
		forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
	}

	char single_step()
	{
		Tuple!(string,int) de = death_move(g);
		char c = act(g, de[0], de[1]);
		force(c);
		return c;
	}

	void force(char c)
	{
		if(c != 'A')
			g.command(c);
	}

	Tuple!(Pos, int)[] log;
	bool[][] forbidden_cell;

	char act(const(Game) g, string death, int breath)
	{
		const Pos    ro = g.map.robot;
		const Pos    li = g.map.lift;
		Pos[] la = g.map.lambdas();
		sort!((Pos a,Pos b){
			int ad=abs(a.y-li.y)+abs(a.x-li.x);
			int bd=abs(b.y-li.y)+abs(b.x-li.x);
			return ad>bd;;
		})(la);
		Pos[] ra = g.map.razors();
		const(Pos)[] hi = g.map.objects('W');

		Tuple!(char,int)[] cand;
		char c = 'W';
		if( g.map.collected_lambda == g.map.total_lambda ) {
			cand = search(g, ro, [li], death);
		} else if( !la.empty ){
			cand ~= search(g, ro, la~ra, death);
		}

		// 'higesori' mode
		if( !hi.empty && g.map.razor>0 ) {
			int his = 0;
			for(int dy=-1; dy<=+1; ++dy)
			for(int dx=-1; dx<=+1; ++dx)
				if(g.map[ro.y+dy,ro.x+dx] == 'W')
					his++;

			if(his>=2 || his==hi.length)
				cand = [tuple('S',int.max)];
			if(cand.empty) {
				const(Pos)[] tgt;
				for(int y=1; y<=g.map.H; ++y)
				for(int x=1; x<=g.map.W; ++x)
					if(g.map[y,x]=='.'||g.map[y,x]==' ') {
						his = 0;
						for(int dy=-1; dy<=+1; ++dy)
						for(int dx=-1; dx<=+1; ++dx)
							if(g.map[y+dy,x+dx] == 'W')
								his++;
						if(his>=2)
							tgt ~= new Pos(y,x);
					}
				cand ~= search(g, ro, tgt, death, true);
			}
		}

		// 'dig' mode
		if(cand.empty) {
			const(Pos)[] tgt;
			for(int y=1; y<=g.map.H; ++y)
			for(int x=1; x<=g.map.W; ++x)
				if(g.map[y,x]=='.')
					if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
					 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
						tgt ~= new Pos(y,x);
			cand ~= search(g, ro, tgt, death, true);
		}

		if(cand.empty) {
			choke_count++;
			cand ~= tuple('W',int.max);
		}
		sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
			if(c1[1] != c2[1])
				return c1[1] < c2[1];
			return c1[0] < c2[0];
		})(cand);
		c = cand[0][0];

		if(death.count(c) || wait_count>=2) {
			foreach(char live; "UDLRW")
				if(death.count(live)==0) {
					c=live;
					break;
				}
		}

		if(c == 'W')
			wait_count++;
		else
			wait_count = 0;
		if(wait_count==2)
			c = 'A';
		if(choke_count >= g.map.H)
			c = 'A';

		bool[char] choice;
		foreach(t; cand)
			choice[t[0]] = true;
		log ~= tuple(ro.clone(), cast(int)choice.length);
		if(log.length > 5)
			log = log[$-5..$];
		int cnt = 0;
		foreach(l; log)
			if(l[0] == log[$-1][0])
				++cnt;
		if( cnt >= 3 && breath==1 ) {
			forbidden_cell[ro.y][ro.x] = true;
		}

		return c;
	}

	Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
	{
		bool danger(int y, int x)
		{
			if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
				return false;
			if(is_rocky(g.map[y+1,x]))
				return true;
			if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
			  && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(is_rocky(g.map[y+1,x+1]) && is_rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
			  && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
				return true;
			if(is_rocky(g.map[y,x+1]) && is_rocky(g.map[y-1,x+1]) && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
				return true;
			return false;
		}

		// avoid directly below '*'
		Tuple!(char,int)[] tryA() {
			const(Pos)[] q;
			foreach(p; gs)
				if(!danger(p.y,p.x))
					q ~= p;
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			foreach(p; q) v[p.y][p.x]=true;
			for(int step=1; q.length; ++step) {
				Pos[] q2;
				foreach(p; q) {
					int[] yyy=[p.y-1,p.y+1,p.y,p.y];
					int[] xxx=[p.x,p.x,p.x-1,p.x+1];
					for(int i=0; i<yyy.length; ++i) {
						int y = yyy[i];
						int x = xxx[i];
						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
								yyy ~= ppp.y;
								xxx ~= ppp.x;
							}
							continue;
						}
						if(v[y][x]) continue;
						if(y==s.y && x==s.x && i<4) {
							char c = "UDRL"[i];
							if( death.count(c) == 0 )
								return [tuple(c,step)];
						} else if(forbidden_cell[y][x]){
						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
							if(danger(y,x))
								continue;
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}

		// any empty space is my ground
		Tuple!(char,int)[] tryB() {
			const(Pos)[] q;
			foreach(p; gs) q ~= p;
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			foreach(p; q) v[p.y][p.x]=true;
			for(int step=10; q.length; ++step) {
				Pos[] q2;
				foreach(p; q) {
					int[] yyy=[p.y-1,p.y+1,p.y,p.y];
					int[] xxx=[p.x,p.x,p.x-1,p.x+1];
					for(int i=0; i<yyy.length; ++i) {
						int y = yyy[i];
						int x = xxx[i];
						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
								yyy ~= ppp.y;
								xxx ~= ppp.x;
							}
							continue;
						}
						if(v[y][x]) continue;
						if(y==s.y && x==s.x && i<4) {
							char c = "UDRL"[i];
							if( death.count(c) == 0 )
								return [tuple(c,step)];
						} else if(forbidden_cell[y][x]){
						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}

		// push rocks!
		Tuple!(char,int)[] tryC() {
			const(Pos)[] q;
			foreach(p; gs) q ~= p;
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			foreach(p; q) v[p.y][p.x]=true;
			for(int step=20; q.length; ++step) {
				Pos[] q2;
				foreach(p; q) {
					int[] yyy=[p.y-1,p.y+1,p.y,p.y];
					int[] xxx=[p.x,p.x,p.x-1,p.x+1];
					for(int i=0; i<yyy.length; ++i) {
						int y = yyy[i];
						int x = xxx[i];
						if(is_rocky(g.map[p])) {
							if(i>=4)continue;
							if(y!=p.y)continue;
							if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
						}
						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
								yyy ~= ppp.y;
								xxx ~= ppp.x;
							}
							continue;
						}
						if(v[y][x]) continue;
						if(y==s.y && x==s.x && i<4) {
							char c = "UDRL"[i];
							if( death.count(c) == 0 )
								return [tuple(c,step)];
						} else if(forbidden_cell[y][x]){
						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||is_rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}
		return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
	}
}

class 侵掠如火(SubSolver) : Solver
{
	// Parameters.
	int            PredictFuture = 10;
	const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
	const          ReplanLength  = 400; // O(PF*RCP*RL*SubSolver.single_step)

	Game      current_game;
	SubSolver sub_solver;

	enum {Tentative, Tentative_Stuck, Fixed};
	string plan;
	int    plan_state;
	int    replan_limit;
	bool   lambda_getter;
	int    clear_improvement = 3;

	this(in Game g)
	{
		current_game = g.clone();
		plan         = "";
		plan_state   = Tentative;
		if(g.map.W*g.map.H <= 400) {
			RandomChoicePattern = ["UU","UD","UL","UR",
			                       "DU","DD","DL","DR",
			                       "LU","LD","LL","LR",
			                       "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
			PredictFuture = 20;
			clear_improvement = 1;
		}
		else if(g.map.W*g.map.H <= 4096) {
			RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
			PredictFuture = 10;
			clear_improvement = 0;
		}
		else {
			RandomChoicePattern = ["U","D","L","R"];
			PredictFuture = 10;
			clear_improvement = 0;
		}

		replan_limit = PredictFuture;
	}

	char single_step()
	{
		if(current_game.dead || current_game.cleared)
			return 'A';

		// Make enough prediction.
		while( plan_state==Tentative && plan.length<replan_limit )
			single_step_predict();

		// If the future is bad, correct.
		if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
			replan();

		// Follow the predicted plan.
		if( plan.empty )
			return 'A';
		char c = plan[0];
		plan = plan[1..$];
		int b_lambda = current_game.map.collected_lambda;
		current_game.command(c);
		int a_lambda = current_game.map.collected_lambda;
		if(b_lambda < a_lambda) lambda_getter = false;
		return c;
	}

	void force(char c)
	{
		if(plan.length>0 && plan[0]==c)
		{
			// If matching the plan, just go forward.
			plan = plan[1..$];
		}
		else
		{
			// Discard the plan, otherwise.
			plan_state = Tentative;
			plan       = "";
			sub_solver = null;
		}
		current_game.command(c);
	}

	void single_step_predict()
	{
		if(sub_solver is null) {
			sub_solver = new SubSolver(current_game);
			plan       = "";
		}

		char c = sub_solver.single_step();
		if(c == 'A')
			plan_state = Tentative_Stuck;
		else {
			plan ~= c;
			if(sub_solver.g.cleared) {
				if(clear_improvement-->0) {
					plan_state = Tentative_Stuck;
					replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
				} else {
					plan_state = Fixed;
				}
			} else {
				plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
			}
		}
	}

	void replan()
	{
		// Try to replace every step of the plan by another move.
		Game g = current_game.clone();
		Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
		int insertion_point = plan.length;
		bool tiebreak_by_turn = false;
		int consider_length = min(ReplanLength, g.map.W*g.map.H);
		if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);

		for(int i=0; i<plan.length; ++i) {
			foreach(string prefix; RandomChoicePattern)
				if(prefix[0] != plan[i]) {
					Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
					r[1] = plan[0..i] ~ prefix ~ r[1];
					bool better = false, tbt=false;
					if(!cand[0].g.cleared && r[0].g.cleared)
						better = true;
					else if(cand[0].g.cleared && r[0].g.cleared) {
						better = cand[0].g.score < r[0].g.score;
					}
					else if(!cand[0].g.cleared && !r[0].g.cleared) {
						if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
							better = true;
						else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
							if(cand[0].g.dead && !r[0].g.dead)
								better = true;
							else if(cand[0].g.dead == r[0].g.dead) {
								better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
								tbt = true;
							}
						}
					}
					if(better) {
						cand = r;
						tiebreak_by_turn = true;
						insertion_point = i+prefix.length;
						if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
					}
				}
			g.command(plan[i]);
		}

		if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
			sub_solver   = cand[0];
			plan         = cand[1];
			plan_state   = Tentative_Stuck;
			replan_limit = min(plan.length - insertion_point, PredictFuture);
			lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
		} else {
			sub_solver   = cand[0];
			plan         = cand[1];
			plan_state   = (plan.length < PredictFuture ? Fixed : cand[2]);
			replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
			lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
		}
	}

	Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
	{
		if(consider_length<=0) consider_length = 2;

		SubSolver s = new SubSolver(g);
		foreach(char c; prefix)
			s.force(c);
		string log;
		int state = Tentative;
		while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
			char c = s.single_step();
			if( c == 'A' ) {
				state = Tentative_Stuck;
				break;
			}
			log ~= c;
		}
		if(s.g.cleared) state = Fixed;
		else if(s.g.dead) state = Tentative_Stuck;
		return tuple(s, log, state);
	}
}

class Queue(T)
{
	alias Tuple!(T,int) t;

	t[] cur, next;

	void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
	bool empty() { return cur.empty; }
	t pop() {
		t v = cur[0]; cur = cur[1..$];
		if(cur.empty) { cur = next; next = null; }
		return v;
	}
}

class 疾如風 : Solver
{
	Game g;
	this(in Game g)
	{
		this.g = g.clone();
	}

	char single_step()
	{
		auto dm = death_move(g);

		char c = think(g, dm[0]);
		if(c == 'W') {
			wait_counter++;
			if(dm[0].count(c) || wait_counter>=3) {
				c = 'A';
				foreach(char cc; "DLRU")
					if(dm[0].count(cc) == 0)
						c = cc;
			}
			if(wait_counter > 20)
				c = 'A';
		} else {
			wait_counter = 0;
		}
		if(c != 'A')
			g.command(c);
		return c;
	}

	void force(char c)
	{
		if(c != 'A')
			g.command(c);
	}

	int wait_counter = 0;

	char think(in Game g, string death)
	{
		auto Q = new Queue!(Tuple!(Pos,Pos));
		Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
		Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
		while(!Q.empty) {
			auto tup = Q.pop();
			Pos  p    = tup[0][0];
			Pos  prev = tup[0][1];
			int  dist = tup[1];
			if(V[p.y][p.x])
				continue;
			V[p.y][p.x] = prev;
			if(g.map[p]=='\\' || g.map[p]=='O')
			{
				Pos goback(Pos p) {
					return V[p.y][p.x];
				}
				for(;;) {
					Pos q = goback(p);
					if(q == g.map.robot)
						if(q.y==p.y)
							return q.x<p.x ? 'R' : 'L';
						else
							return q.y<p.y ? 'U' : 'D';
					p=q;
				}
			}

			int[4] dy=[-1,+1,0,0];
			int[4] dx=[0,0,-1,+1];
			char[] ds=['D','U','L','R'];
			for(int i=0; i<4; ++i) {
				if(g.map.robot==p && death.count(ds[i]))
					continue;
				int y=p.y+dy[i], x=p.x+dx[i];
				if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O')&&!V[y][x]) {
					Q.push(tuple(new Pos(y,x),p), dist+1);
				}
			}
		}

		return 'W';
	}
}

//alias 侵掠如火!(疾如風) MainSolver;
//alias 侵掠如火!(徐如林) MainSolver;
alias 疾如風 MainSolver;
//alias 徐如林 MainSolver;
//alias 不動如山 MainSolver;
