这个好像要容易些。
/* ID: qq104801 LANG: C++ TASK: frameup QQ: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 Training Grader Results 14 users online CHN/4 IND/4 KGZ/2 MKD/1 NED/1 USA/1 VNM/1 USER: cn tom [qq104801] TASK: frameup LANG: C++ Compiling... Compile: OK Executing... 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.ABAA D.BBBB.A DDDDAD.A E...AAAA EEEEEE.. ------- test 2 ---- 3 3 AAA A.A AAA ------- test 3 ---- 5 7 AAA.CCC A.A.C.C AABBBCC ..B.B.. ..BBB.. ------- test 4 ---- 11 8 UUUUU... U...U... U...EEEE U...E..E UMMMM..E UMUUMEEE .MJJJJJJ .MJ.M..J .MJ.M..J .MJMM..J ..JJJJJJ ------- test 5 ---- 6 9 AAABBBCCC AQAQQQCQC AAABBBCCC XQXYYYZQZ XQQYQYQQZ XXXYYYZZZ ------- test 6 ---- 20 20 AAABCDEFGHIJKLMNOPQR A.ABCDEFGHIJKLMNOPQR AAABCDEFGHIJKLMNOPQR BBBBCDEFGHIJKLMNOPQR CCCCCDEFGHIJKLMNOPQR DDDDDDEFGHIJKLMNOPQR EEEEEEEFGHIJKLMNOPQR FFFFFFFFGHIJKLMNOPQR GGGGGGGGGHIJKLMNOPQR HHHHHHHHHHIJKLMNOPQR IIIIIIIIIIIJKLMNOPQR JJJJJJJJJJJJKLMNOPQR KKKKKKKKKKKKKLMNOPQR LLLLLLLLLLLLLLMNOPQR MMMMMMMMMMMMMMMNOPQR NNNNNNNNNNNNNNNNOPQR OOOOOOOOOOOOOOOOOPQR PPPPPPPPPPPPPPPPPPQR QQQQQQQQQQQQQQQQQQQR RRRRRRRRRRRRRRRRRRRR ------- test 7 ---- 30 30 ...............OOOOO.......... ...............O...O.......... ...............O...O.......... ...............O...O.......... ...............O...O.......... ...............O...O.......... ...............O...O.......... EEEEEEEEEEEEEEEOEEEOEEEEEEEEEE E..............OOOOO.........E E............................E EEIIUUUUUUUUUUUUUUUUUUUUUUUUEE ..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!
原文：http://www.cnblogs.com/dpblue/p/3986209.html
