「AOJ1151~1160」の編集履歴(バックアップ)一覧に戻る
AOJ1151~1160」を以下のとおり復元します。
*aoj1156
動的計画法で解ける簡単な問題。
普通に解くと少し遅いので優先順位付きキューとメモ化を使って気持ち高速化して解く。
平均的な速度とメモリ使用量で解けた。


 #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()){
	}
 }

復元してよろしいですか?