「AOJ1141～1150」の編集履歴（バックアップ）一覧に戻る

AOJ1141～1150 - (2012/07/18 (水) 10:39:42) のソース

*1150 Cliff Climbing
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150
崖登りミニゲームの最短クリア時間をシミュレートする問題。
盤面も小さいので油断していつも通りMapと優先順位付きキューによる幅優先探索で挑んだらまあまあの結果になった。
片足の位置情報と次どちらの足を使うかの情報以外いらないという点に気づけば平均的なコード実行速度を叩きだせる。
問題はどうやってTop10入りをするかである。



 #include<stdio.h>
 #include<map>
 #include<set>
 #include<queue>
 #include<algorithm>
 #include <stdlib.h>
 #include<vector>
 struct point{
	int x,y;
	bool operator<(const point& p)const{
		if(x!=p.x)return x<p.x;
		return y<p.y;
	}
 };
 struct state{
	int x,y,turn,LR;//-1なら左足、1なら右足を動かす
 };
 class turnSorter {
	public:
	bool operator()(const state& l, const state& r) const {
		return l.turn>r.turn;
  	}
 };
 class posSorter {
	public:
	bool operator()(const state& l, const state& r) const {
		if(l.x!=r.x)return l.x<r.x;
		if(l.y!=r.y)return l.y<r.y;
		return l.LR<r.LR;
  	}
 };
 void setData(int w,int h){
	std::map<state,int,posSorter> memo;
	std::priority_queue<state,std::vector<state>,turnSorter> pQ;
	char map[62][32],c,ts[2];
	state s,nextS;
	s.turn=0;
	std::set<point> goals;
	point p;
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			scanf("%s",ts);
			map[y][x]=ts[0];
			if('0'<=map[y][x]&&map[y][x]<='9')map[y][x]-='0';
			if(map[y][x]=='X')map[y][x]=-1;//-1は進入不可
			if(map[y][x]=='S'){
				map[y][x]=0;
				s.x=x;
				s.y=y;
				s.LR=1;
				pQ.push(s);
				s.LR=-1;
				pQ.push(s);
			}
			if(map[y][x]=='T'){
				map[y][x]=0;
				p.x=x;
				p.y=y;
				goals.insert(p);
			}
		}
	}
	//スタートの設定
	int dxs[]={1,1,1, 1, 1,2,2, 2,3};//右足の移動、xに-1を掛けて左足に転用する
	int dys[]={2,1,0,-1,-2,1,0,-1,0};//9マス
	bool goalOK=false;
	//メモ化による枝刈つき幅優先探索
	while(!pQ.empty()){
		s=pQ.top();
		pQ.pop();
		p.x=s.x;
		p.y=s.y;
		if(goals.find(p)!=goals.end()){
			goalOK=true;
			break;
		}
		if(memo.find(s)!=memo.end()&&memo[s]<s.turn)continue;
		memo[s]=s.turn;
		nextS.LR=-s.LR;
		for(int i=0;i<9;i++){
			nextS.x=s.x+dxs[i]*s.LR;
			nextS.y=s.y+dys[i];
			if(nextS.x<0 || w<=nextS.x || nextS.y<0 || h<=nextS.y || map[nextS.y][nextS.x]==-1)continue;
			nextS.turn=s.turn+map[nextS.y][nextS.x];
			if(memo.find(nextS)!=memo.end()&&memo[nextS]<=nextS.turn)continue;
			memo[nextS]=nextS.turn;
			pQ.push(nextS);
		}
	}
	printf("%d\n",goalOK?s.turn:-1);
 }
 int main(){
	int h,w;
	while(1){
		scanf("%d %d",&w,&h);
		if(w==0&&h==0)break;
		setData(w,h);
	}
 }