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

AOJ1141~1150 - (2012/07/18 (水) 10:39:42) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *1150 Cliff Climbing
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150
-崖登りのミニゲームの最短クリア時間をシミュレートする問題。
-盤面も小さいので油断していつも通りMapと優先順位付きキューによる幅優先探索で挑んだら惨敗した。
-コード実行速度最下位クラスでは合格しても何の意味もない。
-やはり狙うなら実行速度Top10である。
-とりあえず考えるのは探索を止めてもっと動的計画法の側面を強くしてメモ化による枝刈も配列になおすとか?
+崖登りミニゲームの最短クリア時間をシミュレートする問題。
+盤面も小さいので油断していつも通り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なら右足を動かす
+	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.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;
+		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;
-	std::vector<int> startXs,startYs;
+	s.turn=0;
 	std::set<point> goals;
-	point p,p2;
+	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;
-				startXs.push_back(x);
-				startYs.push_back(y);
+				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);
 			}
 		}
 	}
 	//スタートの設定
-	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()){
+		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;
-		s.LR=-s.LR;
+		nextS.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];
-			}
+			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);
 	}
  }