//mazetest
var debugline = "DEBUG:\n";


var input = '\
**************************\
*S* *                    *\
* * *  *  *************  *\
* *   *    ************  *\
*    *                   *\
************** ***********\
*                        *\
** ***********************\
*      *              G  *\
*  *      *********** *  *\
*    *        ******* *  *\
*       *                *\
**************************';





var Maze = function() {
	this.o = new Array(13);
	this.ot = new Array(13);
	this.setup();
}

Maze.prototype = {
	setup: function(input) {
		var self = this;
		//makeMaze(input);
	},
	makeMaze: function(input) {
		var self = this;
		var counter = 0;
		for (var i=0;i<13;i++) {
			self.o[i] = new Array(26);
			for (var j=0;j<26;j++) {
				self.o[i][j] = input.charAt(counter++);
			}
		}
	},
	printMaze: function(id,text) {
		var self = this;
		var output = 'maze '+text+"\n";
		for (var i=0;i<13;i++) {
			output += '<div class="mazeline">';
			for (var j=0;j<26;j++) {
				if(self.o[i][j] == '*') {
					output += '<span class="wall"></span>';
				} else if(self.o[i][j] == ' ') {
					output += '<span class="road"></span>';
				} else if(self.o[i][j] == 'G') {
					output += '<span class="goal"></span>';
				} else if(self.o[i][j] == 'S') {
					output += '<span class="start"></span>';
				} else if(self.o[i][j] == 'f') {
					output += '<span class="footmark"></span>';
				} else if(self.o[i][j] == 'c') {
					output += '<span class="footmark2"></span>';
				} else if(self.o[i][j] == 'd') {
					output += '<span class="footmark3"></span>';
				}
			}
			output += "</div>";
		}
		
		$("#"+id).html($("#"+id).html()+output);
	},
	remakeMaze: function() {
		var self = this;
		var flagOfEnd = 1;
		
		do {
			self.makeMazeTemp();
			
			//三方ふさがりを壁化
			//***
			//* *
			do {
				flagOfWall = 0;
				for (var i=1;i<12;i++) {
					for (var j=1;j<25;j++) {
						if(self.o[i][j] == ' ') {
							if (self.checkType1(i,j)) {
								self.o[i][j] = '*';
								flagOfWall = 1;
								i=9999;j=9999;
							}
						}
					}
				}
			} while (flagOfWall == 1);
			
			//対角に空白のある角を壁化
			//***
			//*  
			//*  
			
			do {
				flagOfWall = 0;
				for (var i=1;i<12;i++) {
					for (var j=1;j<25;j++) {
						if(self.o[i][j] == ' ') {
							if (self.checkType2(i,j)) {
								self.o[i][j] = '*';
								flagOfWall = 1;
								i=9999;j=9999;
							}
						}
					}
				}
			} while (flagOfWall == 1);
			
			
			if( self.checkRemakeMaze() == 1 ) flagOfEnd = 0;
		} while (flagOfEnd == 1);
	},
	makeMazeTemp: function() {
		var self = this;
		var temp;
		var counter = 0;
		for (var i=0;i<13;i++) {
			self.ot[i] = new Array(26);
			for (var j=0;j<26;j++) {
				temp = self.o[i][j];
				self.ot[i][j] = temp;
			}
		}
	},
	checkType1: function(i,j) {
		var self = this;
		var wallcount = 0;
		
		if(self.o[i][j]==' ') {
			if (self.o[i-1][j] == '*') wallcount++;
			if (self.o[i+1][j] == '*') wallcount++;
			if (self.o[i][j-1] == '*') wallcount++;
			if (self.o[i][j+1] == '*') wallcount++;
			if(wallcount ==3) return 1;
		}
		return 0;
	},
	checkType2: function(i,j) {
		var self = this;
		var pattern = [
			[0,2,0],
			[2,1,1],
			[0,1,1]
		];
		var calc;
		var flagOfMatch = 0;
		
		var mazetemp = self.setMazeTemp(i,j);
		
		for (var n=0;n<4;n++) {
			var flagOfMatch = 1;
			for (var k=0;k<=2;k++) {
				for (var l=-0;l<=2;l++) {
					calc = pattern[k][l]*mazetemp[k][l];
					if( calc == 2) flagOfMatch = 0;
				}
			}
			if(flagOfMatch) {
				//debugline +="[!"+i+':'+j+':'+maze[i][j]+']';
				return 1;
			}
			pattern = self.rotate(pattern);
		}
		
		return 0;
	},
	rotate: function(arr) {
		var temp = [
			[arr[2][0],arr[1][0],arr[0][0]],
			[arr[2][1],arr[1][1],arr[0][1]],
			[arr[2][2],arr[1][2],arr[0][2]]
		];
		
		return temp;
	},
	setMazeTemp: function(i,j) {
		var self = this;
		var temp = [
			[self.o[i-1][j-1],self.o[i-1][j],self.o[i-1][j+1]],
			[self.o[i][j-1],self.o[i][j],self.o[i][j+1]],
			[self.o[i+1][j-1],self.o[i+1][j],self.o[i+1][j+1]]
		];
		
		for (var i=0;i<=2;i++) {
			for (var j=-0;j<=2;j++) {
				if (temp[i][j] == '*') {
					temp[i][j] = 2;
				} else {
					temp[i][j] = 1;
				}
			}
		}
		return temp;
	},
	checkRemakeMaze: function() {
		var self = this;
		
		for (var i=1;i<12;i++) {
			for (var j=1;j<25;j++) {
				if( self.o[i][j] != self.ot[i][j] ) {
					return 0;
				}
			}
		}
		return 1;
	},
	clone: function(obj) {
		var self = this;
		var temp;
		
		obj.o = new Array(13);
		for (var i=0;i<13;i++) {
			obj.o[i] = new Array(26);
			for (var j=0;j<26;j++) {
				temp = self.o[i][j];
				obj.o[i][j] = temp;
			}
		}
		return 1;
	}
}



var Pointer = function(maze) {
	this.x = 0;
	this.y = 0;
	this.sx = 0;
	this.sy = 0;
	this.gx = 0;
	this.gy = 0;
	this.count = 0;
	this.mincount = 9999;
	this.flag = new Array();
	this.history = new Array();
	this.maze = new Maze();
	this.bestmaze = new Maze();
	this.setup(maze);
}

Pointer.prototype = {
	setup: function(maze) {
		var self = this;
		if ( (maze === undefined)||(maze === null) ) { return 0;}
		//スタートゴール設定
		for (var i=1;i<12;i++) {
			for (var j=1;j<25;j++) {
				if( maze.o[i][j] == 'S' ) {
					self.sx = i;
					self.sy = j;
				} else if( maze.o[i][j] == 'G' ) {
					self.gx = i;
					self.gy = j;
				}
			}
		}
		self.maze = maze;
	},
	moveNext: function(nx,ny) {
		var self = this;
		
		var flagOfGoal= 0;
		var countOfWay = 0;
		
		self.x = nx;
		self.y = ny;
		self.maze.o[self.x][self.y] = 'f';
		//debugline +='['+self.x+':'+self.y+'@'+self.count+"]\n";
		//$("#debug").html("<pre>"+debugline+"</pre>");
		
		do {
			countOfWay = 0;
			self.flag['U'] = 0;
			self.flag['D'] = 0;
			self.flag['L'] = 0;
			self.flag['R'] = 0;
			try { if ( self.maze.o[self.x-1][self.y] == ' ' ) { countOfWay++; self.flag['U']=1; } } catch(e) {debugline += "e1\n";}
			try { if ( self.maze.o[self.x+1][self.y] == ' ' ) { countOfWay++; self.flag['D']=1; } } catch(e) {debugline += "e1\n";}
			try { if ( self.maze.o[self.x][self.y-1] == ' ' ) { countOfWay++; self.flag['L']=1; } } catch(e) {debugline += "e1\n";}
			try { if ( self.maze.o[self.x][self.y+1] == ' ' ) { countOfWay++; self.flag['R']=1; } } catch(e) {debugline += "e1\n";}
			
			if(countOfWay == 0) {
				debugline += 'X';
				debugline += '^';
				var popTemp = self.history.pop();
				if ( (popTemp !== undefined)&&(popTemp !== null) ) {
					popTemp.maze.clone(self.maze);
					self.x = popTemp.x;
					self.y = popTemp.y;
					self.count = popTemp.count;
					self.flag['U'] = popTemp.fU;
					self.flag['D'] = popTemp.fD;
					self.flag['L'] = popTemp.fL;
					self.flag['R'] = popTemp.fR;
					debugline += " ret]"+self.x+':'+self.y+'@'+self.history.length+'>'+self.flag['U']+'-'+self.flag['D']+'-'+self.flag['L']+'-'+self.flag['R']+"\n";
					
					self.flag['U'] = 0;
					self.flag['D'] = 0;
					self.flag['L'] = 0;
					self.flag['R'] = 0;
					try { if ( self.maze.o[self.x-1][self.y] == ' ' ) { countOfWay++; self.flag['U']=1; } } catch(e) {debugline += "e1\n";}
					try { if ( self.maze.o[self.x+1][self.y] == ' ' ) { countOfWay++; self.flag['D']=1; } } catch(e) {debugline += "e1\n";}
					try { if ( self.maze.o[self.x][self.y-1] == ' ' ) { countOfWay++; self.flag['L']=1; } } catch(e) {debugline += "e1\n";}
					try { if ( self.maze.o[self.x][self.y+1] == ' ' ) { countOfWay++; self.flag['R']=1; } } catch(e) {debugline += "e1\n";}
				} else {
					debugline += 'finish';
				}
			}
			if(countOfWay > 1) {
				debugline += "[sep]"+self.x+':'+self.y+'>'+self.flag['U']+'-'+self.flag['D']+'-'+self.flag['L']+'-'+self.flag['R']+"\n";
				self.maze.o[self.x][self.y] = 'c';
				var mazeTemp = new Maze();
				self.maze.clone(mazeTemp);
				
				
				if (self.flag['U']) {
					mazeTemp.o[self.x-1][self.y] = 'd'
					self.history.push({ maze:mazeTemp, x:self.x, y:self.y, count:self.count, fU:0, fD:self.flag['D'], fL:self.flag['L'], fR:self.flag['R'] });
					self.count++;
					debugline += '>move]'+(self.x-1)+':'+self.y+"\n";
					self.moveNext(self.x-1,self.y);
					debugline +='&lt;U';
					
				} else if (self.flag['D']) {
					mazeTemp.o[self.x+1][self.y] = 'd'
					self.history.push({ maze:mazeTemp, x:self.x, y:self.y, count:self.count, fU:0, fD:0, fL:self.flag['L'], fR:self.flag['R'] });
					self.count++;
					debugline += '>move]'+(self.x+1)+':'+self.y+"\n";
					self.moveNext(self.x+1,self.y);
					debugline +='&lt;D';
					
				} else if (self.flag['L']) {
					mazeTemp.o[self.x][self.y-1] = 'd'
					self.history.push({ maze:mazeTemp, x:self.x, y:self.y, count:self.count, fU:0, fD:0, fL:0, fR:self.flag['R'] });
					self.count++;
					debugline += '>move]'+self.x+':'+(self.y-1)+"\n";
					self.moveNext(self.x,self.y-1);
					debugline +='&lt;L';
					
				} else if (self.flag['R']) {
					mazeTemp.o[self.x][self.y+1] = 'd'
					self.history.push({ maze:mazeTemp, x:self.x, y:self.y, count:self.count, fU:0, fD:0, fL:0, fR:0 });
					self.count++;
					debugline += '>move]'+self.x+':'+(self.y+1)+"\n";
					self.moveNext(self.x,self.y+1);
					debugline +='&lt;R';
				}
				
			} else if(countOfWay == 1) {
				
				var countOfWay2 = 1;
				var fU = self.flag['U'];
				var fD = self.flag['D'];
				var fL = self.flag['L'];
				var fR = self.flag['R'];
				
				while(countOfWay2 == 1) {
					//一歩進む
					self.count++;
					self.maze.o[self.x][self.y] = 'f';
					if (fU == 1)		{ self.x -= 1; }
					else if (fD == 1)	{ self.x += 1; }
					else if (fL == 1)	{ self.y -= 1; }
					else if (fR == 1)	{ self.y += 1; }
					debugline += '[move]'+self.x+':'+self.y+"\n";
					
					
					//ゴール判定
					flagOfGoal = 0;
					try { if ( self.maze.o[self.x-1][self.y] == 'G' ) { flagOfGoal = 1; } } catch(e) {}
					try { if ( self.maze.o[self.x+1][self.y] == 'G' ) { flagOfGoal = 1; } } catch(e) {}
					try { if ( self.maze.o[self.x][self.y-1] == 'G' ) { flagOfGoal = 1; } } catch(e) {}
					try { if ( self.maze.o[self.x][self.y+1] == 'G' ) { flagOfGoal = 1; } } catch(e) {}
					
					if( flagOfGoal ) {
						debugline += 'G';
						self.count++;
						self.maze.o[self.x][self.y] = 'f';
						if(self.count < self.mincount) {
							self.mincount = self.count;
							self.maze.printMaze('calc',self.mincount+'steps');
							self.maze.clone(self.bestmaze);
						}
					}
					
					//行き止まり判定
					fU=0;
					fD=0;
					fL=0;
					fR=0;
					countOfWay2 = 0;
					try { if ( self.maze.o[self.x-1][self.y] == ' ' ) { countOfWay2++; fU=1; } } catch(e) {}
					try { if ( self.maze.o[self.x+1][self.y] == ' ' ) { countOfWay2++; fD=1; } } catch(e) {}
					try { if ( self.maze.o[self.x][self.y-1] == ' ' ) { countOfWay2++; fL=1; } } catch(e) {}
					try { if ( self.maze.o[self.x][self.y+1] == ' ' ) { countOfWay2++; fR=1; } } catch(e) {}
					countOfWay = countOfWay2;
					//$("#debug2").html($("#debug2").html()+countOfWay2+'@'+self.x+':'+self.y+"+<br>\n");
				}
			}
			
			
		} while(countOfWay > 0);
		
		//self.maze.printMaze('calc',self.mincount+'steps');
		
		//$("#debug2").html($("#debug2").html()+'!');
		return 0;
	},
	printBestMaze: function(id) {
		var self = this;
		var output = 'bestmaze '+self.mincount+"steps\n";
		for (var i=0;i<13;i++) {
			output += '<div class="mazeline">';
			for (var j=0;j<26;j++) {
				if(self.bestmaze.o[i][j] == '*') {
					output += '<span class="wall"></span>';
				} else if(self.bestmaze.o[i][j] == ' ') {
					output += '<span class="road"></span>';
				} else if(self.bestmaze.o[i][j] == 'G') {
					output += '<span class="goal"></span>';
				} else if(self.bestmaze.o[i][j] == 'S') {
					output += '<span class="start"></span>';
				} else if(self.bestmaze.o[i][j] == 'f') {
					output += '<span class="footmark"></span>';
				} else if(self.bestmaze.o[i][j] == 'c') {
					output += '<span class="footmark2"></span>';
				} else if(self.bestmaze.o[i][j] == 'd') {
					output += '<span class="footmark3"></span>';
				}
			}
			output += "</div>";
		}
		
		$("#"+id).html($("#"+id).html()+output);
	}
}







$(document).ready(function(){
	var M = new Maze();
	
	M.makeMaze(input);
	
	
	//整形
	M.printMaze('main','original');
	M.remakeMaze();	//整形まででなんか3時間終わってたよ(ノ∀`)
	M.printMaze('main','remake');
	
	//分岐毎にツリー化……の予定が最後まで
	var P = new Pointer(M);
	P.moveNext(P.sx,P.sy);
	P.printBestMaze('calc');
	
	
	
	
	//$("#debug").html("<pre>"+debugline+"</pre>");
});