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を開くかもしれません。