tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 0209,0213,0243

たまにはパソコン甲子園の過去問でもやることにしました。

0209
回転とかやれば楽。

#include<stdio.h>
#include<algorithm>
using namespace std;
int M[100][100];
int v[100][100];
int x[100][100];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)
			for(int j=0;j<a;j++)
				scanf("%d",&M[i][j]);
		for(int i=0;i<b;i++)
			for(int j=0;j<b;j++)
				scanf("%d",&v[i][j]);
		int row=999999;
		int col=999999;
		for(int i=0;i<4;i++){
			for(int j=0;j<a-b+1;j++)
				for(int k=0;k<a-b+1;k++){
					bool ok=true;
					int D=99999;
					int E=99999;
					for(int l=0;ok&&l<b;l++)
						for(int m=0;ok&&m<b;m++){
							if(~v[l][m]&&v[l][m]!=M[j+l][k+m])ok=false;
							if(~v[l][m]){
								if(D>l+j||(D==l+j&&E>m+k)){
									D=l+j;
									E=m+k;
								}
							}
						}
					if(ok){
				//		printf("%d %d %d %d\n",j,k,D,E);
						if(row>D||(row==D&&col>E)){
							row=D;
							col=E;
						}
					}
				}
			for(int j=0;j<b;j++)
				for(int k=0;k<b;k++)
					x[j][k]=v[k][b-1-j];
			for(int j=0;j<b;j++)
				for(int k=0;k<b;k++)
					v[j][k]=x[j][k];
		}
		if(row==999999)printf("NA\n");
		else printf("%d %d\n",col+1,row+1);
		
	}
}

0213
四角に切れ。僕は手で解くときもこういう方針を使うのが好きです。

#include<stdio.h>
#include<algorithm>
using namespace std;
int s[15];
int m[10][10];
int ans[10][10];
int now[10][10];
int used[15];
int row[15];
int col[15];
int ret;
int a,b,c;
void solve(int x,int y){
	//printf("%d %d\n",x,y);
	if(ret>1)return;
	if(y==a){
		solve(x+1,0);
		return;
	}
	if(x==b){
		ret++;
		for(int i=0;i<b;i++)
			for(int j=0;j<a;j++)
				ans[i][j]=now[i][j];
		return ;
	}
	if(~now[x][y]&&used[now[x][y]]){
		solve(x,y+1);
		return;
	}
	for(int i=0;i<c;i++){
		if(!used[i]&&row[i]>=x&&col[i]>=y){
			for(int j=row[i]-x+1;j*(col[i]-y+1)<=s[i];j++){
				if(s[i]%j==0){
					bool ok=true;
					for(int k=0;k<j;k++){
						for(int l=0;l<s[i]/j;l++){
							if(now[x+k][y+l]!=m[x+k][y+l])ok=false;
						}
					}
					if(ok){
						for(int k=0;k<j;k++){
							for(int l=0;l<s[i]/j;l++){
								now[x+k][y+l]=i;
							}
						}
						used[i]=1;
						solve(x,y+1);
						used[i]=0;
						for(int k=0;k<j;k++){
							for(int l=0;l<s[i]/j;l++){
								now[x+k][y+l]=m[x+k][y+l];
							}
						}
					}
				}
			}
		}
	}
}
int main(){
	while(scanf("%d%d%d",&a,&b,&c),a){
		for(int i=0;i<c;i++){
			int d,e;
			scanf("%d%d",&d,&e);
			s[d-1]=e;
			used[i]=0;
		}
		for(int i=0;i<b;i++)
			for(int j=0;j<a;j++){
				scanf("%d",&m[i][j]);
				m[i][j]--;
				now[i][j]=m[i][j];
				if(m[i][j]>=0){
					row[m[i][j]]=i;
					col[m[i][j]]=j;
				}
			}
		ret=0;
		solve(0,0);
		if(ret==1){
			for(int i=0;i<b;i++){
				for(int j=0;j<a;j++){
					if(j)printf(" ");
					printf("%d",ans[i][j]+1);
				}
				printf("\n");
			}
		}else printf("NA\n");
	}
}

0243
同色パネル結合に似ているが、こっちの方がクソっぽい。反復深化するだけで解ける。

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
struct wolf{
	int m[10][10];
	wolf(){for(int i=0;i<10;i++)for(int j=0;j<10;j++)m[i][j]=0;}
};
int st[10][10];
char str[2];
int a,b;
int ret;
void solve(int t,wolf w){
	//printf("%d\n",t);
	//fflush(stdout);
	if(t>=ret)return;
	bool ok=true;
	for(int i=0;i<b;i++)
		for(int j=0;j<a;j++)
			if(w.m[i][j]!=w.m[0][0])ok=false;
	if(ok){
		ret=t;
		return;
	}
	for(int i=1;i<4;i++){
		if(w.m[0][0]==i)continue;
		wolf D=w;
		queue<pair<int,int> >Q;
		Q.push(make_pair(0,0));
		D.m[0][0]=i;
		//int count=0;
		while(Q.size()){
			int row=Q.front().first;
			int col=Q.front().second;
			Q.pop();
			for(int j=0;j<4;j++)
				if(0<=row+dx[j]&&row+dx[j]<b&&0<=col+dy[j]&&col+dy[j]<a&&w.m[0][0]==D.m[row+dx[j]][col+dy[j]]){
					Q.push(make_pair(row+dx[j],col+dy[j]));
					//count++;
					D.m[row+dx[j]][col+dy[j]]=i;
				}
		}
		solve(t+1,D);
	}
}
int main(){
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<b;i++)
			for(int j=0;j<a;j++){
				scanf("%s",str);
				if(str[0]=='R')st[i][j]=1;
				if(str[0]=='G')st[i][j]=2;
				if(str[0]=='B')st[i][j]=3;
			}
		ret=a+b;
		wolf S;
		for(int i=0;i<b;i++)
			for(int j=0;j<a;j++)
				S.m[i][j]=st[i][j];
		for(int i=0;;i++){
			ret=i+1;
			solve(0,S);
			if(ret<=i)break;
		}
		printf("%d\n",ret);
	}
}

PCKのunsolvedは25問になりました。埋めるためにまたVirtual Arenaでunsolved contestを開くかもしれません。