import util;

////////////////////////////////////////////////////////////////////////////////

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=='\\';
}

////////////////////////////////////////////////////////////////////////////////

class Pos
{
	public immutable int y, x;
	mixin DeriveCreate;
	mixin DeriveCompare;
	mixin DeriveShow;
	Pos clone() const { return cast(Pos) this; }

const @property:
	Pos wait()  { return this.clone(); }
	Pos up()    { return new Pos(y+1, x); }
	Pos down()  { return new Pos(y-1, x); }
	Pos left()  { return new Pos(y, x-1); }
	Pos right() { return new Pos(y, x+1); }
	alias wait  W,w;
	alias up    U,u;
	alias down  D,d;
	alias left  L,l;
	alias right R,r;
}

unittest
{
	assert( (new Pos(2,1)).U == new Pos(3,1) );
	assert( (new Pos(0,1)).D == new Pos(-1,1) );
	assert( (new Pos(2,1)).L == new Pos(2,0) );
	assert( (new Pos(2,1)).R == new Pos(2,2) );
	int[Pos] aa;
	aa[new Pos(1,2)] = 1;
	aa[new Pos(1,2)] = 2;
	aa[new Pos(2,1)] = 3;
	assert( aa.length==2 );
	assert( aa[new Pos(1,2)]==2 );
}

////////////////////////////////////////////////////////////////////////////////

class Water
{
	mixin DeriveShow;

private:
	immutable int base, pace;
	mixin DeriveCreate;
	Water clone() const { return cast(Water) this; }

	static load(string[string] params)
	{
		return new Water(params.get("Water",    "0").to!int(),
		                 params.get("Flooding", "0").to!int());
	}

	int level(int turn) const
	{
		return pace ? base+(turn/pace) : base;
	}

	int until_rise(int turn) const
	{
		return pace ? pace-turn%pace : int.max;
	}
}

unittest
{
	Water w = new Water(1, 3);
	assert( 1 == w.level(0) );
	assert( 1 == w.level(1) );
	assert( 1 == w.level(2) );
	assert( 2 == w.level(3) );
	assert( 2 == w.level(4) );
	assert( 2 == w.level(5) );
	assert( 3 == w.level(6) );

	w = new Water(1, 0);
	assert( 1 == w.level(0) );
	assert( 1 == w.level(1) );
	assert( 1 == w.level(2) );
	assert( 1 == w.level(3) );
	assert( 1 == w.level(4) );
	assert( 1 == w.level(5) );
}

////////////////////////////////////////////////////////////////////////////////

class Hige
{
	mixin DeriveShow;

private:
	immutable int pace;
	mixin DeriveCreate;
	Hige clone() const { return cast(Hige)this; }

	static load(string[string] params)
	{
		return new Hige(params.get("Growth", "25").to!int());
	}

	bool is_growing_turn(int turn) const
	{
		return pace ? turn%pace == pace-1 : false;
	}

	int until_rise(int turn) const
	{
		return pace ? pace-turn%pace : int.max;
	}
}

////////////////////////////////////////////////////////////////////////////////

class Trampoline
{
	mixin DeriveShow;

private:
	immutable char[]   target_of_;
	immutable char[][] source_of_;
	immutable Pos[]    position_of_;
	immutable char[]   source_list_;
	immutable char[]   target_list_;
	Trampoline clone() const { return cast(Trampoline) this; }

	this(in Map m, char[char] tramparam)
	{
		auto ta = new char['I'+1];
		auto sr = new char[]['9'+1];
		auto po = new Pos[max('I','9')+1];
		char[] sl, tl;
		foreach(fr,to; tramparam) {
			ta[fr]  = to;
			sr[to] ~= fr;
		}
		for(int y=1; y<=m.H; ++y)
		for(int x=1; x<=m.W; ++x) {
			char c = m[y,x];
			if('A'<=c && c<='I') {
				sl ~= c;
				po[c] = new Pos(y,x);
			}
			if('1'<=c && c<='9') {
				tl ~= c;
				po[c] = new Pos(y,x);
			}
		}
		target_of_ = cast(immutable) ta;
		source_of_ = cast(immutable) sr;
		position_of_ = cast(immutable) po;
		source_list_ = cast(immutable) sl;
		target_list_ = cast(immutable) tl;
	}

public @property const:
	const(char[]) source_list() { return source_list_; }
	const(char[]) target_list() { return target_list_; }
	const(char[]) source_of(char c) { return source_of_[c]; }
	char target_of(char c) { return target_of_[c]; }
	Pos[] source_pos(char c) {
		Pos[] ps;
		foreach(s; source_of(c))
			ps ~= position_of_[s].clone();
		return ps;
	}
	Pos target_pos(char c) { return position_of_[target_of_[c]].clone(); }
}

////////////////////////////////////////////////////////////////////////////////

class Map
{
	mixin DeriveShow;

	private char[][] data;
	Pos robot;
	Pos lift;
	private int waterproof;
	private int collected_razor;
	int collected_lambda;
	int total_lambda;
	private bool cleared;
	private Pos[] may_update;

	private Map clone() const { return new Map(this); }
	private this(in Map m) {
		foreach(s; m.data)
			this.data ~= s.dup;
		this.robot      = m.robot.clone();
		this.lift       = m.lift.clone();
		this.waterproof = m.waterproof;
		this.collected_razor  = m.collected_razor;
		this.collected_lambda = m.collected_lambda;
		this.total_lambda     = m.total_lambda;
		this.cleared    = m.cleared;
		this.may_update = (cast(Map)m).may_update.dup;
	}

	const {
		@property {
			int H() { return data.length; }
			int W() { return data[0].length; }
			int num_razor() { return collected_razor; }

			Pos[] razors()  { return objects('!'); }
			Pos[] lambdas() { return objects('\\'); }
		}

		Pos[] objects(char c) {
			Pos[] ans;
			for(int y=1; y<=H; ++y)
			for(int x=1; x<=W; ++x)
				if(this[y,x] == c)
				ans ~= new Pos(y,x);
			return ans;
		}

		char opIndex(int y, int x) {
			--y, --x;
			if(y<0||H<=y||x<0||W<=x)
				return '#';
			return data[H-1-y][x];
		}

		char opIndex(in Pos p) {
			return this[p.y, p.x];
		}
	}

private:
	this(string[] raw_data, string[string] params, char[char] trampo)
	{
		int width = 0;
		foreach(r; raw_data)
			width = max(width, r.length);
		foreach(r; raw_data) {
			this.data ~= r.dup;
			this.data[$-1].length = width;
			this.data[$-1][r.length..$] = ' ';
		}

		for(int y=1; y<=H; ++y)
		for(int x=1; x<=W; ++x) {
			if(this[y,x] == 'R')
				this.robot = new Pos(y,x);
			if(this[y,x] == 'L' || this[y,x] == 'O')
				this.lift = new Pos(y,x);
			if(this[y,x] == '\\' || this[y,x] == '@')
				total_lambda++;
			if(is_rocky(this[y,x]))
				may_update ~= new Pos(y,x);
		}

		this.waterproof      = params.get("Waterproof", "5").to!int();
		this.collected_razor = params.get("Razors", "0").to!int();
	}

	void opIndexAssign(char c, int y, int x)
	{
		--y, --x;
		if(y<0||H<=y||x<0||W<=x)
			return;
		data[H-1-y][x] = c;
	}

	void opIndexAssign(char c, in Pos p)
	{
		this[p.y, p.x] = c;
	}

	bool command(char c, int turn, bool hige_day, in Trampoline tr)
	{
		switch(c)
		{
		case 'R': return move( 0, +1, hige_day, tr);
		case 'L': return move( 0, -1, hige_day, tr);
		case 'U': return move(+1,  0, hige_day, tr);
		case 'D': return move(-1,  0, hige_day, tr);
		case 'W': return move( 0,  0, hige_day, tr);
		case 'S': return use_razor(hige_day);
		default:  assert(false);
		}
	}

	bool use_razor(bool hige_day)
	{
		if(collected_razor > 0)
		{
			collected_razor--;
			for(int dy=-1; dy<=+1; ++dy)
			for(int dx=-1; dx<=+1; ++dx)
				if(this[robot.y+dy,robot.x+dx] == 'W')
					emptify(new Pos(robot.y+dy,robot.x+dx));
		}
		return update(hige_day);
	}

	// Register a position that may become empty in the last turn.
	void emptify(Pos p)
	{
		this[p] = ' ';
		for(int dy=0;  dy<=+1; ++dy)
		for(int dx=-1; dx<=+1; ++dx)
			may_update ~= new Pos(p.y+dy, p.x+dx);
	}

	bool move(int dy, int dx, bool hige_day, in Trampoline tr)
	{
		Pos next = new Pos(robot.y+dy, robot.x+dx);
		int y=robot.y, x=robot.x;

		if( '\\' == this[next] ) collected_lambda++;
		if(  '!' == this[next] ) collected_razor++;
		if( 'O'  == this[next] ) cleared = true;

		if( is_spacy(this[next]) )
		{
			emptify(robot);
			robot = next;
			this[next] = 'R';
		}
		else if(dy==0 && is_rocky(this[next]) && ' '==this[y+dy*2,x+dx*2])
		{
			char rock  = this[next];
			emptify(robot);
			robot = next;
			this[next]          = 'R';
			this[y+dy*2,x+dx*2] = rock;
			may_update ~= new Pos(y+dy*2,x+dx*2);
		}
		else if(is_trampoline_source(this[next]))
		{
			emptify(robot);
			Pos tp = tr.target_pos(this[next]);
			foreach(p; tr.source_pos(this[tp]))
				emptify(p);
			this[tp] = 'R';
			robot    = tp;
		}
		return update(hige_day);
	}

	bool update(bool hige_day)
	{
		// Write after all the updates are processed.
		Tuple!(int,int,char)[] write_buffer;
		void write(int y, int x, char c) { write_buffer ~= tuple(y,x,c); }
		void writep(Pos p, char c) { write_buffer ~= tuple(0+p.y,0+p.x,c); }
		scope(exit) {
			may_update.length = 0;
			foreach(wr; write_buffer) {
				this[wr[0],wr[1]] = wr[2];
				if(is_rocky(wr[2]))
					may_update ~= new Pos(wr[0],wr[1]);
				if(wr[2]==' ')
					emptify(new Pos(wr[0], wr[1]));
			}
		}

		if(collected_lambda == total_lambda)
			if(this[lift]=='L')
				this[lift] = 'O';

		bool dead = false;
		if( hige_day ) {
			for(int y=1; y<=H; ++y)
			for(int x=1; x<=W; ++x)
				if(this[y,x]=='W')
					may_update ~= new Pos(y,x);
		}

		sort(may_update);
		foreach(p; may_update) {
			int y = p.y, x = p.x;
			char rock = this[p];
			if(is_rocky(this[p])) {
				if(this[p.D]==' ') {
					writep(p, ' ');
					writep(p.D, (rock=='@'&&this[p.D.D]!=' ' ? '\\' : rock));
					if(robot == p.D.D)
						dead=true;
				}
				else if((is_rocky(this[p.D]) || this[p.D]=='\\') && this[p.R]==' ' && this[p.R.D]==' ') {
					writep(p, ' ');
					writep(p.R.D,(rock=='@'&&this[p.R.D.D]!=' ' ? '\\' : rock));
					if(robot == p.R.D.D)
						dead=true;
				}
				else if(is_rocky(this[p.D]) && this[p.L]==' ' && this[p.L.D]==' ') {
					writep(p, ' ');
					writep(p.L.D, (rock=='@'&&this[p.L.D.D]!=' ' ? '\\' : rock));
					if(robot == p.L.D.D)
						dead=true;
				}
			}
			else if(this[p]=='W') {
				if(hige_day) {
					for(int dy=-1; dy<=+1; ++dy)
					for(int dx=-1; dx<=+1; ++dx)
						if(this[p.y+dy,p.x+dx] == ' ') {
							write(p.y+dy,p.x+dx,'W');
							if(robot.y==p.y+dy-1 && robot.x==p.x+dx)
								dead = false; // guarded by hige!
						}
				}
			}
		}

		return dead;
	}
}

////////////////////////////////////////////////////////////////////////////////

class Game
{
	mixin DeriveShow;

	private {
		Map map_;
		Water water_;
		Hige hige_;
		Trampoline tr_;
		int  turn = 0;
		bool dead_ = false;
		int  under_water = 0;
	}

	Game clone() const { return new Game(this); }
	this(in Game g) {
		map_   = g.map_.clone();
		water_ = g.water_.clone();
		hige_  = g.hige_.clone();
		tr_    = g.tr_.clone();
		turn   = g.turn;
		dead_  = g.dead_;
		under_water = g.under_water;
	}

	this(File input)
	{
		string[]       raw_data;
		string[string] params;

		// Raw map data; read until empty line.
		for(string line; !(line=input.readln().chomp()).empty; )
			raw_data ~= line;

		// Additional commands; read until EOF.
		char[char] trampo;
		for(string line; !(line=input.readln()).empty; ) {
			string[] ss = line.split();
			if( ss.length == 2 )
				params[ss[0]] = ss[1];
			if( ss.length == 4 && ss[0]=="Trampoline" && ss[2]=="targets" )
				trampo[ss[1][0]] = ss[3][0];
		}

		this.map_   = new Map(raw_data, params, trampo);
		this.water_ = Water.load(params);
		this.hige_  = Hige.load(params);
		this.tr_    = new Trampoline(this.map, trampo);
	}

	void command(char c)
	{
		assert(c != 'A');
		if(dead || cleared)
			return;

		// TODO: clarify the event order
		bool dead_now = map_.command(c, turn, hige.is_growing_turn(turn), tr);
		if( dead_now )
			dead_ = true;
		if(!map.cleared) {
			if( map.robot.y <= water_level )
				++under_water;
			else
				under_water = 0;
			if( under_water > map.waterproof )
				dead_ = true;
		}
		turn += 1;
	}

@property const:
	long score()           { return map.collected_lambda*(dead?25L:cleared?75L:50L)-turn; }
	int water_level()      { return water.level(turn); }
	int water_until_rise() { return water.until_rise(turn); }
	int hige_until_rise()  { return hige.until_rise(turn); }
	int hp()               { return map.waterproof - under_water; }
	bool cleared()         { return map.cleared; }
	bool dead()            { return dead_; }
	const(Map)        map()   { return map_; }
	const(Water)      water() { return water_; }
	const(Hige)       hige()  { return hige_; }
	const(Trampoline) tr()    { return tr_; }
}
