Index: src/solver.d
==================================================================
--- src/solver.d
+++ src/solver.d
@@ -22,32 +22,40 @@
 
 	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()
 	{
-		char c = act(g, death_move(g));
+		Tuple!(string,int) de = death_move(g);
+		char c = act(g, de[0], de[1]);
 		g.command(c);
 		return c;
 	}
 
-	string death_move(const(Game) g)
+	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 death;
+		return tuple(death, choice);
 	}
 
-	char act(const(Game) g, string death)
+	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;
 
@@ -57,10 +65,11 @@
 			cand = search(g, ro, li, death);
 		} else {
 			foreach(lam; la)
 				cand ~= search(g, ro, lam, death);
 		}
+		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);
@@ -71,10 +80,24 @@
 			if(g_wc > 10)
 				c = 'A';
 		}
 		else
 			g_wc = 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 o, string death)
 	{
@@ -110,10 +133,11 @@
 							if(v[y][x]) continue;
 							if(y==s.y && x==s.x) {
 								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]=='.') {
 								if(danger(y,x))
 									continue;
 								q2 ~= new Pos(y,x);
 								v[y][x]=true;
@@ -129,11 +153,11 @@
 		// any empty space is my ground
 		Tuple!(char,int)[] tryB() {
 			const(Pos)[] q = [o];
 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
 			v[o.y][o.x]=true;
-			for(int step=15; q.length; ++step) {
+			for(int step=10; q.length; ++step) {
 				Pos[] q2;
 				foreach(p; q) {
 					int[] dy=[-1,+1,0,0];
 					int[] dx=[0,0,-1,+1];
 					for(int i=0; i<4; ++i) {
@@ -142,10 +166,11 @@
 						if(v[y][x]) continue;
 						if(y==s.y && x==s.x) {
 							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]=='.') {
 							q2 ~= new Pos(y,x);
 							v[y][x]=true;
 						}
 					}
@@ -158,11 +183,11 @@
 		// push rocks!
 		Tuple!(char,int)[] tryC() {
 			const(Pos)[] q = [o];
 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
 			v[o.y][o.x]=true;
-			for(int step=30; q.length; ++step) {
+			for(int step=20; q.length; ++step) {
 				Pos[] q2;
 				foreach(p; q) {
 					int[] dy=[-1,+1,0,0];
 					int[] dx=[0,0,-1,+1];
 					for(int i=0; i<4; ++i) {
@@ -171,10 +196,11 @@
 						if(v[y][x]) continue;
 						if(y==s.y && x==s.x) {
 							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]=='.') {
 							q2 ~= new Pos(y,x);
 							v[y][x]=true;
 						} else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) {
 							q2 ~= new Pos(y,x);
@@ -184,8 +210,8 @@
 				}
 				q = q2;
 			}
 			return [];
 		}
-		return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max);
+		return tryA() ~ tryB() ~ tryC();
 	}
 }