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

AOJ1151～1160 - (2012/07/18 (水) 18:16:24) のソース

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







*1159　Next Mayor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1159
ちょっとした小石取りゲームをシミュレートする問題。
数式を使うのが一番賢いのだろうけど、そんな方法を思いつきそうもなかったので問題で指定されたルール通り愚直に実装。
賢い方法？なにそれ。


 #include<stdio.h>
 #include<string.h>
 void calc(int n,int p){
	int memo[51],count,p1=0,max=p;
	memset(memo,0,sizeof(memo));
	while(1){
		if(p==0){
			p=memo[p1];
			memo[p1]=0;
		}else{
			memo[p1]++;
			p--;
		}
		if(memo[p1]==max)break;
		p1=(p1+1)%n;
	}
	printf("%d\n",p1);
 }
 int main(){
	int n,p;
	while(1){
		scanf("%d %d",&n,&p);
		if(n==0&&p==0)break;
		calc(n,p);
	}
 }