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

AOJ121～130 - (2011/08/18 (木) 14:08:31) の編集履歴(バックアップ)

---

---

0121　Seven Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
実行速度と分かりやすさのバランスをとって結局こういうコードになった。
このコードなら中学生でもわかるかも。

#include<stdio.h>
#include<queue>
#include<map>
int mod[]={100000000,10000000,1000000,100000,10000,1000,100,10};
int dxs[]={1,4,-1,-4};
int main(){
int num,next,p,np,dell,turn;
   std::queue<int> qu;
   std::map<int,int> memo;
   qu.push(12345670);
   memo[1234567]=0;
   while(qu.empty()==false){
       num=qu.front();
       turn=memo[num/10];
       qu.pop();
       for(int i=0;i<4;i++){
		p=num%10;
		np=p+dxs[i];
		if(np<0 || 7<np || (np==3 && p==4)||(np==4 && p==3))continue;
		dell=((num/mod[np])%10);
		next=(num-dell*mod[np]+dell*mod[p])-num%10+np;
           if(memo.find(next/10)==memo.end()){
               qu.push(next);
               memo[next/10]=turn+1;
           }
       }
}
   	int n;
   	while(scanf("%d",&n)!=EOF){
	for(int i=1;i<8;i++){
		scanf("%d",&p);
		n=n*10+p;
	}
	if(memo.find(n)!=memo.end()){
		printf("%d\n",memo[n]);
	}
}
}

---

0121

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122
データの読み込みでポカミスをして2度連続不正解という大馬鹿をしてしまう。
こんな簡単な問題でポカミスのせいで間違うなんてもったいない。

#include<stdio.h>
#include <stdlib.h>
#include<string.h>
int dxs[]={2,2,1,0,-1,-2,-2,-2,-1,0,1,2};
int dys[]={0,1,2,2,2,1,0,-1,-2,-2,-2,-1};
int px[]={-1,0,1,-1,0,1,-1,0,1};
int py[]={-1,-1,-1,0,0,0,1,1,1};
void setMap(int x,int y){
int nx,ny,ox=x,oy=y,jx,jy,count,n,xx,yy;
scanf("%d",&n);
int map[10][10],nMap[10][10];
memset(map,0,400);
memset(nMap,0,400);


map[y][x]=1;

for(int i=0;i<n;i++){
	scanf("%d %d",&nx,&ny);
	count=0;
	for(int j=0;j<9;j++){
		jx=ox+px[j];
		jy=oy+py[j];
		if(jx<0 || 9<jx || jy<0 || 9<jy || map[jy][jx]==0) continue;
		for(int k=0;k<12;k++){
			xx=jx+dxs[k];
			yy=jy+dys[k];
			if(xx<0 || 9<xx || yy<0 || 9<yy) continue;
			if(abs(xx-nx)<2 && abs(yy-ny)<2){
				nMap[yy][xx]=1;
				count++;
			}
		}
	}
	memcpy(map,nMap,400);
	memset(nMap,0,400);
	ox=nx;
	oy=ny;
}
if(count>0){
	printf("OK\n");
}else{
	printf("NA\n");
}
}
int main(){
int x,y;
while(1){
	scanf("%d %d",&x,&y);
	if(x==0 && y==0) break;
	setMap(x,y);
}
}