首页 > 代码库 > usaco-4.4-frameup-passed
usaco-4.4-frameup-passed
这个好像要容易些。
/*ID: qq104801LANG: C++TASK: frameupQQ:104804687*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>#define rep(i, n) for(int i = 1; i <= n;i++)using namespace std;const int maxn=50;int w,h,p,l[maxn],r[maxn],u[maxn],d[maxn],D[maxn];char map[maxn][maxn],_p[maxn];bool a[maxn],g[maxn][maxn];void dfs(){ bool flag=0; for(int i=1;i<=26;i++) if(a[i]) { flag=1; break; } if(!flag) { for(int i=1;i<=p;i++) cout<<_p[i]; cout<<endl; return; } for(int i=1;i<=26;i++) if(a[i] && D[i]==0) { _p[++p]=i+‘@‘; for(int j=1;j<=26;j++) if(g[i][j]) D[j]--; a[i]=0; dfs(); for(int j=1;j<=26;j++) if(g[i][j]) D[j]++; a[i]=1; p--; } }void test(){ freopen("frameup.in","r",stdin); freopen("frameup.out","w",stdout); cin>>h>>w; char c; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) { cin>>c; map[i][j]=c; if(!l[c-‘@‘] || j<l[c-‘@‘]) l[c-‘@‘]=j; if(!r[c-‘@‘] || j>r[c-‘@‘]) r[c-‘@‘]=j; if(!u[c-‘@‘] || i<u[c-‘@‘]) u[c-‘@‘]=i; if(!d[c-‘@‘] || i>d[c-‘@‘]) d[c-‘@‘]=i; a[c-‘@‘]=1; //cout<<map[i][j]; //if(j==7)cout<<endl; } memset(g,0,sizeof(g)); for(int i=1;i<=26;i++) if(a[i]) { for(int j=l[i];j<=r[i];j++) { if(map[u[i]][j]!=‘.‘) g[i][map[u[i]][j]-‘@‘]=1; if(map[d[i]][j]!=‘.‘) g[i][map[d[i]][j]-‘@‘]=1; } for(int j=u[i];j<=d[i];j++) { if(map[j][l[i]]!=‘.‘) g[i][map[j][l[i]]-‘@‘]=1; if(map[j][r[i]]!=‘.‘) g[i][map[j][r[i]]-‘@‘]=1; } } for(int i=1;i<=26;i++) for(int j=1;j<=26;j++) if(i!=j && g[i][j]) D[j]++; p=0; dfs(); return;}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 14 users onlineCHN/4 IND/4 KGZ/2 MKD/1 NED/1 USA/1 VNM/1USER: cn tom [qq104801]TASK: frameupLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.003 secs, 3380 KB] Test 2: TEST OK [0.003 secs, 3380 KB] Test 3: TEST OK [0.003 secs, 3380 KB] Test 4: TEST OK [0.003 secs, 3380 KB] Test 5: TEST OK [0.003 secs, 3380 KB] Test 6: TEST OK [0.003 secs, 3380 KB] Test 7: TEST OK [0.005 secs, 3380 KB] Test 8: TEST OK [0.092 secs, 3380 KB] Test 9: TEST OK [0.292 secs, 3380 KB]All tests OK.YOUR PROGRAM (‘frameup‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----9 8.CCC....ECBCBB..DCBCDB..DCCC.B..D.B.ABAAD.BBBB.ADDDDAD.AE...AAAAEEEEEE..------- test 2 ----3 3AAAA.AAAA------- test 3 ----5 7AAA.CCCA.A.C.CAABBBCC..B.B....BBB..------- test 4 ----11 8UUUUU...U...U...U...EEEEU...E..EUMMMM..EUMUUMEEE.MJJJJJJ.MJ.M..J.MJ.M..J.MJMM..J..JJJJJJ------- test 5 ----6 9AAABBBCCCAQAQQQCQCAAABBBCCCXQXYYYZQZXQQYQYQQZXXXYYYZZZ------- test 6 ----20 20AAABCDEFGHIJKLMNOPQRA.ABCDEFGHIJKLMNOPQRAAABCDEFGHIJKLMNOPQRBBBBCDEFGHIJKLMNOPQRCCCCCDEFGHIJKLMNOPQRDDDDDDEFGHIJKLMNOPQREEEEEEEFGHIJKLMNOPQRFFFFFFFFGHIJKLMNOPQRGGGGGGGGGHIJKLMNOPQRHHHHHHHHHHIJKLMNOPQRIIIIIIIIIIIJKLMNOPQRJJJJJJJJJJJJKLMNOPQRKKKKKKKKKKKKKLMNOPQRLLLLLLLLLLLLLLMNOPQRMMMMMMMMMMMMMMMNOPQRNNNNNNNNNNNNNNNNOPQROOOOOOOOOOOOOOOOOPQRPPPPPPPPPPPPPPPPPPQRQQQQQQQQQQQQQQQQQQQRRRRRRRRRRRRRRRRRRRRR------- test 7 ----30 30...............OOOOO.........................O...O.........................O...O.........................O...O.........................O...O.........................O...O.........................O...O..........EEEEEEEEEEEEEEEOEEEOEEEEEEEEEEE..............OOOOO.........EE............................EEEIIUUUUUUUUUUUUUUUUUUUUUUUUEE..I.U...I..............AAAAUA...I.U...I..............A...UA...I.U...I..............A...UA...I.UUUUUUUUUUUUUUUUUUUUUUUUA...I.....I..............A....A...I.....I..............A....A...I.....I..............AAAAAA...I.....I.......................I.....I.......................I.....I.......................IIIIIII.....................................................................................................................................................................................................................................................................------- test 8 ----30 30...............................OOOOOOOOOYYYYYOO..............O....PPPPYPPPYPOPP............O....P...Y...Y.O.P............O....P...Y...Y.O.P............O....P...Y...Y.O.P............O....P...Y...Y.O.P............O....P...Y...Y.O.P............O....P...Y...Y.O.P............O....P...Y...Y.O.P............OOOOOOOOOYOOOYOEEEEEEEEE...........PPPPYPPPYPEPP.....E...............Y...Y.E.......E.......WWWWWWWWWWWWWWWWWTT...E.......W...T...Y...Y.E.W.T...E.......W...T...Y...Y.E.W.T...E.......W...T...Y...Y.E.W.T...E.......W...T...YYYYY.EEWEEEEEE.....UUWWWWWWWWWWWWWWWWW.T.........U.....TTTTTTTTTTTTQQQQQQQQQQQ.U....RRRRRRRRRRRRRQRRRRR....Q.U....R............Q....R....Q.UIIIIRRRRRRRRRRRRRQRRRRRIIIIQ.UI................QQQQQQQQQQQ.UUUUUUUUUUUUUUUUUUU........I...IIIIIIIIIIIIIIIIIIIIIIIIIII..........................................................................................................................------- test 9 ----30 30.DDDDRRRRQGGGGGGGGGGGGGQQQQQQ..DSSDRSSSQGSRSSSSS....G.....Q..D..DR...QG.R....SEEEEEEEEE.Q..D..DRTTOOGOOOOOOOEOOOGOOOEOOO.D..DRT.OQG.R....SE...G...ETQO.D..DRT.OIGFFFFFFFEFFFGIIIEIQO.D..DRT.CCCCCCCCCSE..FG...EIQO.D..DRT.CIGFR...CSE..FG...EIQO.D..DRT.CIGFR...CMEMMFGMMMEIMO.DBBBBBBBBBBBBBBBBBBBBBBBBEIMO.DB.DRT.CIGFR...CSE..FG..BEIMO.DBLDLLHCHGFHHLLCLELLFGLOBEIMO.DBLDRTHCIGAAAA.CSE..FGL.BEIM..DBDDRTHCIGARHA.CSE..FGL.BEIM..SBL.RTHCIGARHA.CSE..FGL.BEIM..SBLLLLHCIGALHALCLEKKFGKKBEIM..SB..RTHCIGARHANCNENNFG.KBEIM..SB..RTHCIGARHANCSE..FG.KBEIM..SBBBBBBBBBABBABBBBBBBBBBBEIM..S...RTHCIGAFFAFCFEFFFG.K.EIM..S...RTHCIGAGGAGCGEGGGG.K.EIM..S...RTHCIJAJHANCQEEEEEEEEEIM..S...RTHCI.AJHANCSK..N..K..IM..PPPPPPHCIIAIHAICIIIIIIIIIIIM..P...RTHCHHAHHANCSKKKKKKKTTTM..P...R.JCCCAAAACCS...N......M..P...R.JJJJJJ..NMS...N......M..PSSSRSSSSSSRSSNMMMMMMMMMMMMM..P...RRRRRRRR..N.....N......P..PPPPPPPPPPPPPPNNNNNNNPPPPPPP.Keep up the good work!Thanks for your submission!
usaco-4.4-frameup-passed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。