这个是个图形识别匹配题，有点意思，星空图。旋转，对称翻转，比对。
/* ID: qq104801 LANG: C++ TASK: starry QQ:104804687 */ #include <iostream> #include <fstream> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cmath> using namespace std; #define loop(i,n) for(int i=0;i<(n);i++) const int maxn=101; const int inf=1<<30; int dir[][2]={{0,1},{1,-1},{-1,0},{-1,-1},{0,-1},{-1,1},{1,0},{1,1}};//方向向量 typedef char skymap[maxn][maxn]; struct node { skymap im; int ih,iw; }hash[26],com; skymap start,final,now; int h,w,len; void flood(skymap& ima,int i,int j,int cor[]) { ima[i][j]='0';now[i][j]='1'; cor[0]=min(cor[0],i);cor[1]=min(cor[1],j); cor[2]=max(cor[2],i);cor[3]=max(cor[3],j); loop(k,8) { int r,s; r=dir[k][0]+i;s=dir[k][1]+j; if(r>=0 && r<h && s>=0 && s<w && ima[r][s]=='1') flood(ima,r,s,cor); } } void change() //rotate 90 degree { skymap a; memcpy(a,com.im,sizeof(a)); for(int i=0;i<=com.ih;i++) for(int j=0;j<=com.iw;j++) com.im[j][com.ih-i]=a[i][j]; int t=com.ih; com.ih=com.iw; com.iw=t; } void turn() //asystemetric trun { for(int i=0;i<=com.ih/2;i++) for(int j=0;j<=com.iw;j++) { char t=com.im[i][j]; com.im[i][j]=com.im[com.ih-i][j]; com.im[com.ih-i][j]=t; } } bool search(int cor[]) { loop(r,2) { if(r==1)turn(); loop(s,4) { if(s!=0)change(); if(cor[2]-cor[0]!=com.ih || cor[3]-cor[1]!=com.iw)continue; bool flag=1; for(int i=cor[0];i<=cor[2] && flag;i++) for(int j=cor[1];j<=cor[3] && flag;j++) if(com.im[i-cor[0]][j-cor[1]]!=now[i][j]) {flag=0;break;} if(flag==1)return true; } } return false; } void insert(int cor[]) { for(int i=cor[0];i<=cor[2];i++) for(int j=cor[1];j<=cor[3];j++) hash[len].im[i-cor[0]][j-cor[1]]=now[i][j]; hash[len].ih=cor[2]-cor[0]; hash[len].iw=cor[3]-cor[1]; } void col(int i,int j,int c) { final[i][j]=(char)('a'+c); loop(k,8) { int r,s; r=dir[k][0]+i;s=dir[k][1]+j; if(r>=0 && r<h && s>=0 && s<w && final[r][s]=='1') col(r,s,c); } } void test() { freopen("starry.in","r",stdin); freopen("starry.out","w",stdout); cin>>w>>h; loop(i,h){ cin>>start[i]; //cout<<start[i]<<endl; } len=0; memcpy(final,start,sizeof(start)); loop(i,h) loop(j,w) if(start[i][j]=='1') { memset(now,'0',sizeof(now)); int cor[]={inf,inf,-1,-1}; flood(start,i,j,cor); bool flag=0; int k=0; for(k;k<len;k++) { memcpy(com.im,hash[k].im,sizeof(com.im)); com.ih=hash[k].ih;com.iw=hash[k].iw; if(search(cor)){flag=1;break;} } if(flag==0) { memset(hash[len].im,'0',sizeof(start)); insert(cor); len++; } col(i,j,k); } loop(i,h) { cout<<final[i]<<endl; } } int main () { test(); return 0; }
test data:
USACO Training Grader Results 22 users online CHN/16 NCL/1 RUS/1 TJK/3 USA/1 USER: cn tom [qq104801] TASK: starry LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.011 secs, 3672 KB] Test 2: TEST OK [0.011 secs, 3672 KB] Test 3: TEST OK [0.014 secs, 3672 KB] Test 4: TEST OK [0.014 secs, 3672 KB] Test 5: TEST OK [0.049 secs, 3672 KB] All tests OK. YOUR PROGRAM ('starry') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations. Here are the test data inputs: ------- test 1 ---- 10 10 0000000000 0000000000 0000000000 0000000000 0111110000 0111110000 0111110000 0000000000 0000000000 0000000000 ------- test 2 ---- 20 10 00000000000000000000 01110000001110000010 00000000001010001000 00000000000000011000 01111000110000000000 00000000110000010000 00000000000000010000 00000010000001110000 01111100011111000000 00000000000000000000 ------- test 3 ---- 20 15 00000010000000010000 01110000001110000010 00000000001010001000 00000000000000011000 01111000110000000010 00000000110000010000 10010000000000010000 00000010000001110000 01111100011111000000 00000000000000000000 01111000000000011100 00100010000110010100 00000110000110000000 00010000000000000100 11111111111111111111 ------- test 4 ---- 23 16 11111111111111111111111 10000000000000000000001 10001000010100010011001 10001000000100000100001 10100100011111000001001 10000000000000001001001 10010001011111001010001 10000110000100001000001 10000000010101000000001 10111000000000110010001 10000011100000000001001 10000000000101001001001 10001100001001000000001 10010001001001001110001 10000000000000000000001 11111111111111111111111 ------- test 5 ---- 84 80 101101101101101101101101101100101010010101001010100101010000101010001111111111110011 000000000000000000000000000000000000000000000000000000000010000000001000000000010011 010101001010100101010110110110110110110110000000010101000010000000001010101000010011 000000000000000000000000000000000000000000000000000000000010000000001000000000010011 000000001100010000010000100000100000010000010000000000011111110000001000000000010011 000101001100001000101001010001010000101000101001010000000010000000001000010000010011 000010000000001000010000100000100000010000010000100000010010000100001000111000010011 000101000000001000000000000000000000000000000001010000010010000110001000010000010011 000000000000000100100000101010000001010000000000000000010000100110001001000010010011 001000001010100000001000000000000000100000001010000011111110100010001000000000010011 000000000000000000000000000000000001010000000100000000010000100000001111111111110011 111111111111111111111111111111110000000000001010000000010111111100000000000000000011 000000000000000000000000000000000000000100000000000000010000100000000101010000010011 110110110110110110110110110110110000111000000010100110000000100111000000000000010011 000000000000000000000000000000000001000000000001000110000000100011100000000000010011 100100100100000000000000000000000000000000000010100000000000000000000000000000010011 000000000000001010000110110110110110110110000000000000011101110111011101110111010011 010100000000000100000000000000000000000000000110000001110111011101110111011100010011 001000000000001010000110110110110110110110000000000000000000000000000000000000010011 010100000101000000100000000000000000000000011001010000001001001001000000001000010011 000000000111000001110000111111111111000110000000100000000000000000000000001000010011 000000000010000000000000100000000001000110000001010000000010010010010000011000010011 101000000000000100010100100001000001000000000000000000010000000000000000010000010011 010000010000001110001000100001000001000001010010100000100000000000000000011000010011 101000111000001010010100100001000001000000100001000000100010100001010000001000010011 000000101000000000000000101111111001000001010010100000100001000000100000011000010011 101000000000000000000000100001000001000000000000000001000010100001010000010000010011 010000110000110000101000100001000001000100000000000000000000000000000000011000010011 101001100000011000010000100001001001001110000001001001001000000000000000001000010011 000000110000110000101000100000000001000100000000000000000000000001000000011000010011 000000000000000000000000111111111111000000110110110110110110110001001000010000010011 000000111000001000110000000000000000000000110110110110110110110001110000011000010011 011100000000001000000000001001001001000000000000000000000000000000000000001000010011 001000001010001001110000000000000000000000000000000000000000000000000000011000010011 000000011011000000100010000001010101010101010101011101110111011101110000010000010011 001000001010011100000111000001110111011101110111001000100010001000100000011000010011 011100000000001000000000001001010101010101010101011101110111011101110000001000010011 000000000000000000100010001100000000000000000000000000000000000000000000011000010011 100000000000010001110010001000100000000000000000010010010010000011100110010000010011 100100001000110000100010000000000000100001000000000000000000000100100000011000010011 111000000000010000000000000000000000111001110010101000000011110000100000001000010011 000000001000000010000010010010010000100001000000000000000000000110001100011000010011 111000000000000100000000000000000000000000001001001001000000000000000000010000010011 000000000000000100000010001001000100100100100000000000001101100010100110010000010011 111011101110000111000111000000000000000000001001001001000000000001000000000000000011 011011000111000000000010000100000010100111000000000000000010100010100001010011100011 000000000000000000000000000100100001000110000000000000000001000000000000100000100011 110110110110110110110000000111000010100000100100100100000010100110110001010000100011 000000000000000000000000000000000000000000000000000000000000000000000000000000000011 100010000000000100000000010001000000000010000000001000100000000001000000000111100011 011111000111110001011010001111100011111000101101000111110001111100010110100000000011 010000000100010001111110001000000010001000111111000100000001000100011111100000000011 000000000101010001011110000000000010101000101111000000000001010100010111100000000011 000001110100010000000000110000111010001000000000000000011101000100000000000111100011 000010010111110011011000000001001011111000000110000000100101111100000010000000000011 100000010000000000000000010000001000000000000110001000000100000000000000000111100011 001010000001111100100000000101000000111110010000000010100000011111001000000000000011 000010000001000100111110000001000000100010011111001000100000010001001111100111100011 110000011101010101000100000000001110101010100010000000000111010101010001000000000011 000001001101000100000000000000100110100010000000010000010011010001000000000111100011 000100011101111100001110000010001110111110000010000001000111011111000000000000000011 001000011100000001000000000100001110000000100000000010000111000000010000000111100011 000010001000010001001010000001000100001000100101000000100010000100010010100000000011 110000011100010001110000100000001110001000111000010000000111000100011100000111100011 000000000000000000000000000000000000000000000000000000000000000000000000000000000011 100010000000000100000000010001000000000010000000001000100000000001000000000111100011 011111000111110001011010001111100011111000101101000111110001111100010110100000000011 010000000100010001111110001000000010001000111111000100000001000100011111100111100011 000000000101010001011110000000000010101000101111000000000001010100010111100000000011 000001110100010000000000000000111010001000000000000000011101000100000000000111100011 000010010111110000011000000001001011111000000000000000100101111100000000000000000011 100000010000000000000000010000001000000000000000001000000100000000000000000111100011 001010000001111100100000000101000000111110010000000010100000011111001000000000000011 000010000001000100111110000001000000100010011111000000100000010001001111100111100011 000000011101010101000100000000001110101010100010000000000111010101010001000000000011 000001001101000100000000000000100110100010000000000000010011010001000000000111100011 000100011101111100000110000010001110111110000011000001000111011111000000000000000011 001000011100000001000000000100001110000000100000000010000111000000010000000111100011 000010001000010001001010000001000100001000100101000000100010000100010010100000000011 000000011100010001110000110000001110001000111000001100000111000100011100000111100011 Keep up the good work! Thanks for your submission!