2000db1.c

// 2000 domestic B
// 隣が同じ物を見つけたら、すぐに取り去って詰めていくように作った
// 実際はバックトラックにしないといけない

#include <stdio.h>

#define ON  1
#define OFF 0

#define X 4
#define Y 5
#define N X*Y

// 2次元座標を1次元配列用に変換
#define p(x,y) ((x)+(y*X))

// 隣の方向の数(8方向)
#define TONARI 8
// 隣の場所の座標 上の段、同じ段、下の段
int tx[TONARI]={-1, 0,+3,-1,+1,-1, 0,+1};
int ty[TONARI]={-1,-1,-1, 0, 0,+1,+1,+1};
short c[N]; // 場
int nokori; // 残った数のカウント

void push(short c[N]);
void pop(short c[N]);

int sp=0;	 // スタックポインタ
char st[1000][N]; // スタック

void print(void);
void check(int z);
int rearrange(void);

int main(void)
{
	short c2[N]; // 一つ前の場
	int n,i,a,x,y,z;
	int kotae;
	
	scanf("%d", &n);
	printf("n=%d\n", n);
	
	// 読み込み
	for(z=0; z<n; z++){
		printf("\n(%d)\n", z+1);
		for(i=0; i<N; i++){
			scanf("%d", &a);
			c[i]=a;
		}
		
		print();
		puts("-");
		
		kotae=N;
		for(i=0; i<N; i++){
			printf("start(%d,%d)\n",i%X,i/X);
			nokori=N;
			push(c);
			check(i);
			pop(c);
			printf("%d:nokori=%d\n", nokori);
			if(kotae>nokori){
				kotae=nokori;
			}
		}
		printf("kotae=%d\n", kotae);
	}
	
	return(0);
}

void check(int z)
{
	int i,x,y,xx,yy;
	
//	for(i=1; i<z; i++){
//		printf(" ");
//	}
//	if(z) printf("%d\n", z);
	
	if(z<N){
		x=z%X;
		y=z/X;
		for(i=0; i<TONARI; i++){
			xx=x+tx[i];
			yy=y+ty[i];
			if(xx>=0 && yy>=0 && x<X && y<Y){
				if( c[p(x,y)] && ( c[p(x,y)]==c[p(xx,yy)] ) ){ // 隣で同じ物が見つかったら
					int count;
//					printf("(%d,%d)=(%d,%d)=%d\n",x,y,xx,yy,c[p(x,y)]);
					c[p(x,y)]=c[p(xx,yy)]=0;
					count=rearrange(); // 0を後に持っていく＆残りの枚数を数える
					if(nokori>count){
						nokori=count; // 残りの枚数の最小なのを求める
					}
//					print();
					push(c);
					check(z++);
					pop(c);
				}
			}
		}
//		push(c);
//		check(z++);
//		pop(c);
	}
}

void push(short c[N])
{
	int i;
	for(i=0; i<N; i++){
		st[sp][i]=c[i];
	}
	sp++;
}

void pop(short c[N])
{
	int i;
	--sp;
	for(i=0; i<N; i++){
		c[i]=st[sp][i];
	}
}

int rearrange(void)
{
	int i,m=0;
	
	for(i=0; i<N; i++){
		if(c[i]!=0){
			c[m]=c[i];
			m++;
		}
	}
	for(i=m; i<N; i++){
		c[i]=0;
	}
//	printf("remain:%d\n",m);
	return(m);
}

void print(void)
{
	int x, y;
	
	for(y=0; y<Y; y++){
		for(x=0; x<X; x++){
			printf("%d ", c[x+y*X]);
		}
		printf("\n");
	}
}

/*
// 解けたかどうかチェック
int solve(short c[N])
{
	int i,sum=0;
	
	for(i=0; i<N; i++){
		sum+=c[i];
	}
	if(sum==0){
		return(ON);
	}else{
		return(OFF);
	}
}

int stop(short c1[N], short c2[N])
{
	int i,flag=OFF;
	
	for(i=0; i<N; i++){
		if(c1[i]!=c2[i]){
			flag=ON;
		}
		c2[i]=c1[i];
	}
	return(flag);
}


*/