※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ1141~1150」の編集履歴(バックアップ)一覧に戻る

AOJ1141~1150 - (2012/07/17 (火) 11:29:08) の編集履歴(バックアップ)


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 rx,ry,lx,ly,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.rx!=r.rx)return l.rx<r.rx;
	if(l.ry!=r.ry)return l.ry<r.ry;
	if(l.lx!=r.lx)return l.lx<r.lx;
	if(l.ly!=r.ly)return l.ly<r.ly;
	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;
std::vector<int> startXs,startYs;
std::set<point> goals;
point p,p2;
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;
			startXs.push_back(x);
			startYs.push_back(y);
		}
		if(map[y][x]=='T'){
			map[y][x]=0;
			p.x=x;
			p.y=y;
			goals.insert(p);
		}
	}
}
//スタートの設定
s.turn=0;
int x1,y1,x2,y2;
for(int i=0;i<startXs.size();i++){
	s.lx=startXs[i];
	s.ly=startYs[i];
	s.rx=startXs[i];
	s.ry=startYs[i];
	s.LR=-1;//次が右足を動かす
	pQ.push(s);
	s.LR=1;//次は左足を動かす
	pQ.push(s);
}
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.rx;
	p.y =s.ry;
	p2.x=s.lx;
	p2.y=s.ly;
	//printf("<lx=%d ly=%d rx=%d ry=%d lr=%d> ",s.lx,s.ly,s.rx,s.ry,s.turn);
	if(goals.find(p)!=goals.end()||goals.find(p2)!=goals.end()){
		goalOK=true;
		break;
	}
	if(memo.find(s)!=memo.end()&&memo[s]<s.turn)continue;
	memo[s]=s.turn;
	s.LR=-s.LR;
	for(int i=0;i<9;i++){
		nextS=s;
		//ここ綺麗な記述じゃないとは思いつつ書いてしまった。
		if(s.LR==-1){
			nextS.lx=s.rx-dxs[i];
			nextS.ly=s.ry+dys[i];
			if(nextS.ly<0|| h<=nextS.ly || nextS.lx<0 || w<=nextS.lx ||map[nextS.ly][nextS.lx]==-1)continue;
			nextS.turn+=map[nextS.ly][nextS.lx];
		}else{
			nextS.rx=s.lx+dxs[i];
			nextS.ry=s.ly+dys[i];
			if(nextS.ry<0|| h<=nextS.ry || nextS.rx<0 || w<=nextS.rx ||map[nextS.ry][nextS.rx]==-1)continue;
			nextS.turn+=map[nextS.ry][nextS.rx];
		}
		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);
}
}