USACO Section 4.4 Frame Up - DFS即可~

无敌大水题一道...只可惜我太粗心了送了3次WA和1次爆数组才给过...囧..开始题目看错了...题目是要求出所有的涂色方案...并且按字典序输出..一种方案输出一行~~

数据范围很小阿..整个图也就30*30...所出现的也就A-Z的26个大写字母..而且还没有重复...为了方便搜索..我在开始就记录好了A-Z矩形方框的X,Y最大值和最小值~~也就是定位好了每个框框...然后就一个个枚举的DFS了....判断当前是不是在最外层就是扫四个线..这道题可能不好处理的就是当确定了一个框框时如何给抹去回到更早的状态..我就是将其框框都赋值为'?'..后面在判断的时候多加上去就好了...

还有就是不知道如何保证输出顺序..因为实际上找到一组解后要倒过来输出才是结果...所以我干脆都记录下来..排序后再输出...

Program：

/* ID: zzyzzy12 LANG: C++ TASK: frameup */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node { int MaxX,MaxY,MinX,MinY; }letter[30]; struct node1 { char s[35][35]; }h; int H,W,num,way[30],ansnum; string ans[10001]; bool used[35]; void DFS(int step,node1 h) { int k,i; node1 p; if (step>num) { ans[++ansnum]=""; for (k=num;k>=1;k--) ans[ansnum]+=way[k]+'A'; return; } for (k=0;k<26;k++) if (!used[k]) { for (i=letter[k].MinX;i<=letter[k].MaxX;i++) { if (h.s[letter[k].MaxY][i]!='?' && h.s[letter[k].MaxY][i]!=k+'A') goto A; if (h.s[letter[k].MinY][i]!='?' && h.s[letter[k].MinY][i]!=k+'A') goto A; } for (i=letter[k].MinY;i<=letter[k].MaxY;i++) { if (h.s[i][letter[k].MinX]!='?' && h.s[i][letter[k].MinX]!=k+'A') goto A; if (h.s[i][letter[k].MaxX]!='?' && h.s[i][letter[k].MaxX]!=k+'A') goto A; } p=h; for (i=letter[k].MinX;i<=letter[k].MaxX;i++) { p.s[letter[k].MaxY][i]='?'; p.s[letter[k].MinY][i]='?'; } for (i=letter[k].MinY;i<=letter[k].MaxY;i++) { p.s[i][letter[k].MaxX]='?'; p.s[i][letter[k].MinX]='?'; } way[step]=k; used[k]=true; DFS(step+1,p); used[k]=false; A: ; } } int main() { freopen("frameup.in","r",stdin); freopen("frameup.out","w",stdout); scanf("%d%d",&H,&W); int i,j; for (i=1;i<=H;i++) scanf("%s",h.s[i]+1); for (i=0;i<26;i++) { letter[i].MaxX=-oo; letter[i].MaxY=-oo; letter[i].MinX=oo; letter[i].MinY=oo; } memset(used,true,sizeof(used)); for (i=1;i<=H;i++) for (j=1;j<=W;j++) if (h.s[i][j]!='.') { if (letter[h.s[i][j]-'A'].MaxX<j) letter[h.s[i][j]-'A'].MaxX=j; if (letter[h.s[i][j]-'A'].MaxY<i) letter[h.s[i][j]-'A'].MaxY=i; if (letter[h.s[i][j]-'A'].MinX>j) letter[h.s[i][j]-'A'].MinX=j; if (letter[h.s[i][j]-'A'].MinY>i) letter[h.s[i][j]-'A'].MinY=i; used[h.s[i][j]-'A']=false; } num=0; for (i=0;i<26;i++) if (!used[i]) num++; ansnum=0; DFS(1,h); sort(ans+1,ans+1+ansnum); for (i=1;i<=ansnum;i++) { for (j=0;j<num;j++) printf("%c",ans[i][j]); printf("\n"); } return 0; }