首页 > 代码库 > usaco-5.1-starry-passed
usaco-5.1-starry-passed
这个是个图形识别匹配题，有点意思，星空图。旋转，对称翻转，比对。
/*ID: qq104801LANG: C++TASK: starryQQ: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 TrainingGrader Results 22 users onlineCHN/16 NCL/1 RUS/1 TJK/3 USA/1USER: cn tom [qq104801]TASK: starryLANG: C++Compiling...Compile: OKExecuting... 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 ----10100000000000000000000000000000000000000000011111000001111100000111110000000000000000000000000000000000------- test 2 ----201000000000000000000000011100000011100000100000000000101000100000000000000000011000011110001100000000000000000011000001000000000000000000010000000000100000011100000111110001111100000000000000000000000000------- test 3 ----2015000000100000000100000111000000111000001000000000001010001000000000000000000110000111100011000000001000000000110000010000100100000000000100000000001000000111000001111100011111000000000000000000000000000111100000000001110000100010000110010100000001100001100000000001000000000000010011111111111111111111------- test 4 ----231611111111111111111111111100000000000000000000011000100001010001001100110001000000100000100001101001000111110000010011000000000000000100100110010001011111001010001100001100001000010000011000000001010100000000110111000000000110010001100000111000000000010011000000000010100100100110001100001001000000001100100010010010011100011000000000000000000000111111111111111111111111------- test 5 ----8480101101101101101101101101101100101010010101001010100101010000101010001111111111110011000000000000000000000000000000000000000000000000000000000010000000001000000000010011010101001010100101010110110110110110110110000000010101000010000000001010101000010011000000000000000000000000000000000000000000000000000000000010000000001000000000010011000000001100010000010000100000100000010000010000000000011111110000001000000000010011000101001100001000101001010001010000101000101001010000000010000000001000010000010011000010000000001000010000100000100000010000010000100000010010000100001000111000010011000101000000001000000000000000000000000000000001010000010010000110001000010000010011000000000000000100100000101010000001010000000000000000010000100110001001000010010011001000001010100000001000000000000000100000001010000011111110100010001000000000010011000000000000000000000000000000000001010000000100000000010000100000001111111111110011111111111111111111111111111111110000000000001010000000010111111100000000000000000011000000000000000000000000000000000000000100000000000000010000100000000101010000010011110110110110110110110110110110110000111000000010100110000000100111000000000000010011000000000000000000000000000000000001000000000001000110000000100011100000000000010011100100100100000000000000000000000000000000000010100000000000000000000000000000010011000000000000001010000110110110110110110110000000000000011101110111011101110111010011010100000000000100000000000000000000000000000110000001110111011101110111011100010011001000000000001010000110110110110110110110000000000000000000000000000000000000010011010100000101000000100000000000000000000000011001010000001001001001000000001000010011000000000111000001110000111111111111000110000000100000000000000000000000001000010011000000000010000000000000100000000001000110000001010000000010010010010000011000010011101000000000000100010100100001000001000000000000000000010000000000000000010000010011010000010000001110001000100001000001000001010010100000100000000000000000011000010011101000111000001010010100100001000001000000100001000000100010100001010000001000010011000000101000000000000000101111111001000001010010100000100001000000100000011000010011101000000000000000000000100001000001000000000000000001000010100001010000010000010011010000110000110000101000100001000001000100000000000000000000000000000000011000010011101001100000011000010000100001001001001110000001001001001000000000000000001000010011000000110000110000101000100000000001000100000000000000000000000001000000011000010011000000000000000000000000111111111111000000110110110110110110110001001000010000010011000000111000001000110000000000000000000000110110110110110110110001110000011000010011011100000000001000000000001001001001000000000000000000000000000000000000001000010011001000001010001001110000000000000000000000000000000000000000000000000000011000010011000000011011000000100010000001010101010101010101011101110111011101110000010000010011001000001010011100000111000001110111011101110111001000100010001000100000011000010011011100000000001000000000001001010101010101010101011101110111011101110000001000010011000000000000000000100010001100000000000000000000000000000000000000000000011000010011100000000000010001110010001000100000000000000000010010010010000011100110010000010011100100001000110000100010000000000000100001000000000000000000000100100000011000010011111000000000010000000000000000000000111001110010101000000011110000100000001000010011000000001000000010000010010010010000100001000000000000000000000110001100011000010011111000000000000100000000000000000000000000001001001001000000000000000000010000010011000000000000000100000010001001000100100100100000000000001101100010100110010000010011111011101110000111000111000000000000000000001001001001000000000001000000000000000011011011000111000000000010000100000010100111000000000000000010100010100001010011100011000000000000000000000000000100100001000110000000000000000001000000000000100000100011110110110110110110110000000111000010100000100100100100000010100110110001010000100011000000000000000000000000000000000000000000000000000000000000000000000000000000000011100010000000000100000000010001000000000010000000001000100000000001000000000111100011011111000111110001011010001111100011111000101101000111110001111100010110100000000011010000000100010001111110001000000010001000111111000100000001000100011111100000000011000000000101010001011110000000000010101000101111000000000001010100010111100000000011000001110100010000000000110000111010001000000000000000011101000100000000000111100011000010010111110011011000000001001011111000000110000000100101111100000010000000000011100000010000000000000000010000001000000000000110001000000100000000000000000111100011001010000001111100100000000101000000111110010000000010100000011111001000000000000011000010000001000100111110000001000000100010011111001000100000010001001111100111100011110000011101010101000100000000001110101010100010000000000111010101010001000000000011000001001101000100000000000000100110100010000000010000010011010001000000000111100011000100011101111100001110000010001110111110000010000001000111011111000000000000000011001000011100000001000000000100001110000000100000000010000111000000010000000111100011000010001000010001001010000001000100001000100101000000100010000100010010100000000011110000011100010001110000100000001110001000111000010000000111000100011100000111100011000000000000000000000000000000000000000000000000000000000000000000000000000000000011100010000000000100000000010001000000000010000000001000100000000001000000000111100011011111000111110001011010001111100011111000101101000111110001111100010110100000000011010000000100010001111110001000000010001000111111000100000001000100011111100111100011000000000101010001011110000000000010101000101111000000000001010100010111100000000011000001110100010000000000000000111010001000000000000000011101000100000000000111100011000010010111110000011000000001001011111000000000000000100101111100000000000000000011100000010000000000000000010000001000000000000000001000000100000000000000000111100011001010000001111100100000000101000000111110010000000010100000011111001000000000000011000010000001000100111110000001000000100010011111000000100000010001001111100111100011000000011101010101000100000000001110101010100010000000000111010101010001000000000011000001001101000100000000000000100110100010000000000000010011010001000000000111100011000100011101111100000110000010001110111110000011000001000111011111000000000000000011001000011100000001000000000100001110000000100000000010000111000000010000000111100011000010001000010001001010000001000100001000100101000000100010000100010010100000000011000000011100010001110000110000001110001000111000001100000111000100011100000111100011Keep up the good work!Thanks for your submission!
usaco-5.1-starry-passed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。