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

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

AOJ1151~1160 - (2012/07/01 (日) 13:58:04) の1つ前との変更点

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

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

-*aoj1156
+*aoj1156 Twirling Robot
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156
+
 動的計画法で解ける簡単な問題。
 普通に解くと少し遅いので優先順位付きキューとメモ化を使って気持ち高速化して解く。
 平均的な速度とメモリ使用量で解けた。
 
 
  #include<stdio.h>
  #include<queue>
  struct point{
 	int x,y,a,cost;
 	bool operator<(const point& p)const{
 		return cost>p.cost;
 	}
  };
  bool calc(){
 	int map[31][31];
 	int arrowChange[5][4]={	{0,1,2,3},
 				{3,0,1,2},
 				{2,3,0,1},
 				{1,2,3,0},
 				{4,4,4,4}};
 	int dxs[5]={1,0,-1,0,0};
 	int dys[5]={0,-1,0,1,0};
 	int colSize,rowSize;
 	int memo[31][31][5];
 	int mymax=1000000;	
 	scanf("%d %d",&colSize,&rowSize);
 	if(rowSize==0&&colSize==0)return false;
 	for(int r=0;r<rowSize;r++){
 		for(int c=0;c<colSize;c++){
 			scanf("%d",&map[r][c]);
 			for(int k=0;k<5;k++)memo[r][c][k]=mymax;
 		}
 	}
 	int costs[4];
 	for(int i=0;i<4;i++)scanf("%d",&costs[i]);
 	memo[0][0][0]=0;
 	std::priority_queue<point> points;
 	point p,nextP;
 	p.x=p.y=p.a=p.cost=0;
 	points.push(p);
 	while(points.empty()==false){
 		p=points.top();
 		//printf("\n(%d %d %d)",p.x,p.y,p.cost);
 		if(p.y==rowSize-1&&p.x==colSize-1){
 			printf("%d\n",p.cost);
 			break;
 		}		
 		points.pop();
 		for(int i=0;i<4;i++){
 			//iは方向転換の命令
 			int nextCost=p.cost;
 			if(map[p.y][p.x]!=i){
 				nextCost+=costs[i];
 			}
 			int nextArrow=arrowChange[i][p.a];
 			nextP.y=p.y+dys[nextArrow];
 			nextP.x=p.x+dxs[nextArrow];
 			nextP.a=nextArrow;
 			nextP.cost=nextCost;
 			//printf("<%d %d %d>",nextP.x,nextP.y,nextP.cost);
 			if(nextP.x<0||nextP.x>=colSize||nextP.y<0||nextP.y>=rowSize)continue;
 			if(nextP.cost>=memo[nextP.y][nextP.x][nextP.a])continue;
 			memo[nextP.y][nextP.x][nextP.a]=nextP.cost;
 			points.push(nextP);
 		}
 	}
 	return true;
  }
  int main(){
 	while(calc()){
 	}
  }