import util;
import game;

class Solver_0
{
	this(const(Game) g) {}
	char single_step() { return 'W'; }
}

class Solver_1
{
	int wait_count = 0;

	Game g;
	this(const(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]);
		g.command(c);
		return c;
	}

	Tuple!(string,int) death_move(const(Game) g)
	{
		string death;
		int choice = 0;
		foreach(char c; "UDLRW") {
			Game gg = g.clone();
			gg.command(c);
			if( !gg.cleared && gg.dead )
				death ~= c;
			else if( gg.map.robot != g.map.robot )
				choice++;
		}
		return tuple(death, choice);
	}

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

	char act(const(Game) g, string death, int breath)
	{
		const Pos   ro = g.map.robot;
		const Pos[] la = g.map.lambdas();
		const Pos   li = g.map.lift;

		Tuple!(char,int)[] cand;
		char c = 'W';
		if( la.empty ) {
			cand = search(g, ro, [li], death);
		} else {
			cand ~= search(g, ro, la, death);
		}
		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(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='*'||g.map[y+1,x+1]=='*'
					 ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*')
						tgt ~= new Pos(y,x);
			cand ~= search(g, ro, tgt, death, true);
		}

		if(cand.empty)
			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)) {
			foreach(char live; "UDLRWA")
				if(death.count(live)==0) {
					c=live;
					break;
				}
		}

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

		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(g.map[y+1,x] == '*')
				return true;
			if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
				return true;
			if(g.map[y,x+1]=='*' && (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.map.tr_source[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]=='.'||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.map.tr_source[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]=='.'||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('1'<=g.map[y,x]&&g.map[y,x]<='9') {
							foreach(ppp; g.map.tr_source[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]=='.'||i>=4) {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						} else if(i<4 && (y-p.y)==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+(y-p.y),x+(x-p.x)]==' '||g.map[y+(y-p.y),x+(x-p.x)]=='R')) {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}
		return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
	}
}

alias Solver_1 MainSolver;
