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

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

aoj2261~2270 - (2012/07/13 (金) 19:02:26) のソース

*2261 [[iwi]]
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261
文字列から部分文字列を取得して左右対称な文字列を作るとき何文字まで作れるかを答える問題。
簡単に正答数を稼げるのはおいしい問題。
短いコードで合格している人がいるがどんなテクニックがあるのか?
左右対称という恣意的なルールを記述するのにどうしたってコード中にその部分の記述がいるはずなのだが?



 #include<stdio.h>
 #include<string.h>
 char text[20];
 int len,ans=0;
 char cpy[20];
 void saiki(int deep,int nowP){
	if(deep==len){
		//左右対称なら奇数になるはず
		char c1,c2;
		bool out=false;
		cpy[nowP]='\0';
		if(nowP%2==1&&nowP>2){
			for(int i=0;i<nowP/2;i++){
				c1=cpy[i];
				c2=cpy[nowP-i-1];
				if(c1=='i'&&c2!='i')out=true;
				if(c1=='w'&&c2!='w')out=true;
				if(c1=='('&&c2!=')')out=true;
				if(c1==')'&&c2!='(')out=true;
				if(c1=='{'&&c2!='}')out=true;
				if(c1=='}'&&c2!='{')out=true;
				if(c1=='['&&c2!=']')out=true;
				if(c1==']'&&c2!='[')out=true;
				if(out==true)return;
			}
			if(strstr(cpy,"iwi")==NULL)return;
			ans=ans>nowP?ans:nowP;
		}
	}else{
		cpy[nowP]=text[deep];//この文字を使う
		saiki(deep+1,nowP+1);
		saiki(deep+1,nowP);
	}
 }
 int main(){
	scanf("%s",text);
	len=strlen(text);
	saiki(0,0);
	printf("%d\n",ans);
 }






*2262 Stopping Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2262
2次元で記述されたジョークコンパイラを実装する問題。

ジョークなので何とも言えない言語ですが一応サイズ制限をなくせばチューリング完全らしいです。
まあ一応理論上はそうなんでしょうね。
過去に同じ状態を通ってないかメモしながら幅優先探索するだけです。


 #include<stdio.h>
 #include<set>
 #include<queue>
 int dxs[]={1,0,-1,0};
 int dys[]={0,-1,0,1};//右、上、左、下の順
 int r,c;
 struct cur{
	int x,y,arrow;//位置と向き
	int num;//メモリの状態
	bool operator<(const cur& c)const{
		if(x!=c.x)return x<c.x;
		if(y!=c.y)return y<c.y;
		if(arrow!=c.arrow)return arrow<c.arrow;
		return num<c.num;
	}
	cur move(int arrow){
		cur re;
		re.x=(x+dxs[arrow]+c)%c;
		re.y=(y+dys[arrow]+r)%r;
		re.arrow=arrow;
		re.num=num;
		return re;
	}
 };
 int main(){
	scanf("%d %d",&r,&c);
	char map[22][22];
	int x,y;
	for(int i=0;i<r;i++){
		scanf("%s",map[i]);
	}
	cur c1,nextC;
	c1.x=c1.y=c1.num=c1.arrow=0;
	std::set<cur> memo;
	std::queue<cur> Q;
	memo.insert(c1);
	Q.push(c1);
	bool stop=false;
	while(Q.empty()==false){
		c1=Q.front();
		Q.pop();
		x=c1.x;
		y=c1.y;
		char com=map[y][x];
		if(com=='@'){
			stop=true;//停止
			break;
		}
		if(com=='?'){
			//4方向全て試す
			for(int i=0;i<4;i++){
				nextC=c1.move(i);
				if(memo.find(nextC)==memo.end()){
					memo.insert(nextC);
					Q.push(nextC);
				}
			}
			continue;
		}
		if(com=='<'){
			nextC=c1.move(2);//左
		}else if(com=='>'){
			nextC=c1.move(0);//右	
		}else if(com=='^'){
			nextC=c1.move(1);//上
		}else if(com=='v'){
			nextC=c1.move(3);//下
		}else if(com=='_'){
			if(c1.num==0)nextC=c1.move(0);//0なら右
			else nextC=c1.move(2);
		}else if(com=='|'){
			if(c1.num==0)nextC=c1.move(3);//0なら下
			else nextC=c1.move(1);
		}else if(com=='.'){
			nextC=c1.move(c1.arrow);//そのまま
		}else if('0'<=com&&com<='9'){
			nextC=c1.move(c1.arrow);
			nextC.num=com-'0';
		}else if(com=='+'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num+1)%16;
		}else if(com=='-'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num-1+16)%16;
		}
		if(memo.find(nextC)==memo.end()){
			memo.insert(nextC);
			Q.push(nextC);
		}
	}
	printf("%s\n",stop?"YES":"NO");
 }