//***************************************************//
//*                                                 *//
//*迷路探索アルゴリズム DEVELOPMENT DATE: 2005/ 3/30*//
//*                                                 *//
//***************************************************//

public class MeiroSearch{
	int m_k[][] = new int[1000][2];													//探索用（経路を記憶しておくための）配列
	int best_k[][] = new int[1000][2];												//最短経路を記憶しておくための探索用の配列
	int m_r[] = new int[1000];														//進んだ方向を記憶しておくための探索用の配列（未探索のマスには-1を格納する）
	int best_cnt = 9999;															//最短経路の地点を通る数
	int cnt;																		//探索する過程で今まで通った地点の数
	int h[][] = {																	//方向テーブルの作成
	            {-1,1,0,0},															  //h[0][0] = -1,h[0][1] = 1,h[0][2] = 0,h[0][3] = 0  
				{0,0,-1,1},															  //h[1][0] = 0,h[1][1] = 0,h[1][2] = -1,h[1][3] = 1
				};																	//縦の長さ
	int tn;																			//横の長さ
	int yn;
	public MeiroSearch(int tate,int yoko){
		tn = tate;																	//縦の長さの設定
		yn = yoko;																	//横の長さの設定
		cnt = 0;																	//cntの初期化
		Kakunou(cnt,1,1);															//スタート位置を探索用の配列に格納する
	}
	
	//****************************************//
	//*               迷路の探索             *//
	//****************************************//
	
	public int [][] Search(int [][] me){											//与えられた迷路を元に最短経路をreturnするメソッド											
		while(cnt != -1){															//全ての経路の可能性を出すまで
			if(m_k[cnt][0] == (tn - 2) && m_k[cnt][1] == (yn - 2)){					  //ゴール位置に到着したら
				if(cnt < best_cnt){														//今探索した経路が最短経路であるとき
					best_cnt = cnt;														 //	
					for(int i = 0;i <= cnt;i++){										 //最短経路を更新する
						best_k[i][0] = m_k[i][0];										 //
						best_k[i][1] = m_k[i][1];										 //
					}
				}
				cnt = cnt - 1;														  //cntを一つ減らし、まだ試行していない迷路の部分を探索し続ける
			}
			int x = m_k[cnt][0];													  //
			int y = m_k[cnt][1];													  //配列から現在の位置、方向の状態を抜き出す。
			int r = m_r[cnt];														  //
			boolean ok = false;														  //探索で新たな道が見つかるか見つからないか判定する変数
			for(int i = r + 1;(!ok && i < 4);i++){									  //
				if(me[x + h[0][i]][y + h[1][i]] == 0){								  //対象としているマスの上下左右の順で調べていく	
					boolean flg = true;												  //そのマスが壁、外周の壁でなければ、座標を入力する。
					for(int j = 0;j < cnt;j++){										  //
						if(m_k[j][0] == x + h[0][i] && m_k[j][1] == y + h[1][i]){	  //既に探索してあった場所だった時
							flg = false;											    //そこは操作しない
						}															  //
					}
					if(flg){														  //該当するマスが移動可能だった場合
						m_r[cnt] = i;													//m_r[]に方向テーブルの値がセットされている。
						cnt = cnt + 1;													//cntを1増やし、次の探索をさせる。
						Kakunou(cnt,x + h[0][i],y + h[1][i]);							//対象としているマスの情報を記憶しておく
						ok = true;														//新たな道が見つかったので、okをtrueにしておく。
																					  //
					}
				}
			}
			if(!ok){																  //新たな道が見つからなかった時（行き止まりだった時）																 
				cnt = cnt - 1;															//1マス前に戻る。
																					  //
			}
		}
		return best_k;																  //最短経路が格納された情報を返す。
	}
	public void Kakunou(int c,int x,int y){											  //新たな道が見つかった時に、そのマスの情報を記憶するメソッド
		m_k[c][0] = x;																	//そのマスのx座標を記憶する。
		m_k[c][1] = y;																    //そのマスのy座標を記憶する。
		m_r[c] = -1;																	//未探索なので-1を格納する。
	}
}