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

AOJ1000～1010 - (2011/09/12 (月) 13:15:52) のソース

----
*1002　Extraordinary Grid I
格子上に本棚が配置された図書館で最短経路で本を返していく問題。

解法
動的計画法で一列ずつその時点での最短ルートを調べていき更新していくだけです。



 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 void setData(){
	const int rowSize=3,colSize=10002,shelfSize=2;
	int up,down,now,next,shelfs[colSize][shelfSize],memos[colSize][rowSize],tUp,tDown,n,y,x,perm;
    char t;
	scanf("%d",&n);
	memset(memos,0,colSize*rowSize*4);
	memset(shelfs,0,shelfSize*colSize*4);
    scanf("%c",&t);
    for(int i=0;i<n*4;i++){
		y=i/(2*n);
		x=i%(2*n);
		scanf("%c",&t);
		shelfs[(x+1)/2][y]+=(t=='Y'?1:0);
	}
    //0.5を１単位
    for(int i=0;i<rowSize;i++)memos[0][i]=i*2;
	for(int col=0;col<n+1;col++){
		up=down=-1;
		//なんとなく道がｎ行になっても対応できるように
		for(int i=0;i<rowSize-1;i++){
			if(shelfs[col][i]>0){
				up=i*2+1;
				break;
			}
		}
		for(int i=rowSize-2;i>=0;i--){
			if(shelfs[col][i]>0){
				down=i*2+1;
				break;
			}
		}
		for(int i=0;i<rowSize;i++){
			now=i*2;
			if(up==-1)tUp=tDown=now;
			else tUp=up,tDown=down;
			for(int j=0;j<rowSize;j++){
				next=j*2;
				perm=memos[col][i]+abs(now-tUp)+abs(tUp-tDown)+abs(tDown-next)+2;
				if(perm<memos[col+1][j] || memos[col+1][j]==0)memos[col+1][j]=perm;
				perm=memos[col][i]+abs(now-tDown)+abs(tDown-tUp)+abs(tUp-next)+2;
				if(perm<memos[col+1][j])memos[col+1][j]=perm;
			}
		}
    }
    //単位を元に戻して表示
	printf("%d\n",(memos[n+1][0]-2)/2);
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
 }








----
*1003　Extraordinary Grid II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1003
携帯電話の簡易文字入力シミュレーションをする問題。

解法
状態遷移マシーンに食わせて文字列マトリックスと照合指摘吐き出すパイプに文字列を通すだけです。


 #include<stdio.h>
 bool setData(){
	char now='0',old='0',point=0;
	int roops[]={5,6,6,6,6,6,8,6,8};
	char cPuts[10][10]={"',.!?","abcABC","defDEF","ghiGHI","jklJKL","mnoMNO","pqrsPQRS","tuvTUV","wxyzWXYZ"};
	while(now!='\n'){
		if(scanf("%c",&now)==EOF)return false;
		if(now=='0' && old=='0'){
			printf(" ");
		}else if(old=='0' && now!='0'){
			point=0;
		}else if(old==now){
			point=(point+1)%roops[now-'1'];
		}else if(old!=now){
			printf("%c",cPuts[old-'1'][point]);
			point=0;
		}
		old=now;
	}
	printf("\n");
	return true;
 }
 int main(){
	while(setData()){
	}
 }