- 重叠的方框
- 2016-07-02 18:37:26 @
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct rec{
int xmin,xmax,ymin,ymax;
}drec[27];
int n,m;
int alph[27],cnt;
char des[200][200];
char ans[100];
bool relation[26][26];
int in[26];
void dfs(int t)
{
//printf("s");
if(t==cnt)
{
for(int i=0;i<cnt;i++)printf("%c",ans[i]);
printf("\n");
}
else
{
for(int i=0;i<cnt;i++)
{
if(in[i]==0)
{
ans[t]=alph[i]+'A';
in[i]=-1;
for(int j=0;j<cnt;j++)
if(relation[i][j])in[j]--;
dfs(t+1);
in[i]=0;
for(int j=0;j<cnt;j++)
if(relation[i][j])in[j]++;
}
}
}
}
int main()
{
// freopen("rectan8.in","r",stdin);
// freopen("rectan8.out","w",stdout);
bool vis[27]={0};
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",des[i]+1);
for(int j=1;j<=m;j++)
{
if(des[i][j]!='.')
{
int t=des[i][j]-'A';
if(vis[t]==false)alph[cnt++]=t;
vis[t]=1;
if(drec[t].xmin==0||drec[t].xmin>i)drec[t].xmin=i;
if(drec[t].xmax==0||drec[t].xmax<i)drec[t].xmax=i;
if(drec[t].ymin==0||drec[t].ymin>j)drec[t].ymin=j;
if(drec[t].ymax==0||drec[t].ymax<j)drec[t].ymax=j;
}
}
}
//print();
//printf("xmin=%d xmax=%d ymin=%d xmam=%d\n",drec[0].xmin,drec[0].xmax,drec[0].ymin,drec[0].ymax);
sort(alph,alph+cnt);
int temp[27];
for(int i=0;i<cnt;i++)
{
temp[alph[i]]=i;
}
for(int i=0;i<cnt;i++)
{
rec& a=drec[i]; 这行代码写错啦,居然也过啦 正确写法应该是 drec[alph[i]];
int x=a.xmin,y=a.ymin,k=0;
while(y<a.ymax)
{
if(des[x][y]!='A'+alph[i])
{
int g=temp[des[x][y]-'A'];
if(!relation[i][g]){relation[i][g]=1; in[g]++;}
}
y++;
}
while(x<a.xmax)
{
if(des[x][y]!='A'+alph[i])
{
int g=temp[des[x][y]-'A'];
if(!relation[i][g]){relation[i][g]=1; in[g]++;}
}
x++;
}
while(y>a.ymin)
{
if(des[x][y]!='A'+alph[i])
{
int g=temp[des[x][y]-'A'];
if(!relation[i][g]){relation[i][g]=1; in[g]++;}
}
y--;
}
while(x>a.xmin)
{
if(des[x][y]!='A'+alph[i])
{
int g=temp[des[x][y]-'A'];
if(!relation[i][g]){relation[i][g]=1; in[g]++;}
}
x--;
}
}
dfs(0);
return 0;
}