P2741 [USACO4.4]重叠的图像Frame Up[dfs]

题目描述

看下面的五张 9 x 8 的图像:

1
2
3
4
5
6
7
8
9
10
11
........   ........   ........   ........   .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........

1 2 3 4 5

现在,把这些图像按照 1—5 的编号从下到上重叠,第 1 张在最下面,第 5 张在最顶端。如果一张图像覆盖了另外一张图像,那么底下的图像的一部分就变得不可见了。我们得到下面的图像:

1
2
3
4
5
6
7
8
9
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

对于这样一张图像,计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。
下面是这道题目的规则:
矩形的边的宽度为 1 ,每条边的长度都不小于 3 。
矩形的每条边中,至少有一部分是可见的。注意,一个角同时属于两条边。
矩形用大写字母表示,并且每个矩形的表示符号都不相同。

输入输出格式

输入格式:

第一行 两个用空格分开的整数:图像高 H (3 <= H <=30) 和图像宽 W (3 <= W <= 30) 。

第二行到第 H+1 行 H 行,每行 W 个字母。

输出格式:

按照自底向上的顺序输出字母。如果有不止一种情况,按照字典顺序输出每一种情况(至少会有一种合法的顺序)。

输入输出样例

输入样例#1:

9 8
.CCC….
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E…AAAA
EEEEEE..

输出样例#1:

EDABC

说明

题目翻译来自NOCOW。
USACO Training Section 4.4

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/*
ID: ylx14271
PROG: frameup
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){k=k*10+(s-'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,m;
char ch;
char s[40][40];
int map[40][40];
struct node
{
int up,down,left,right;//上、下的横坐标,左、右的纵坐标
node()
{
up=2000000000;
left=2000000000;
down=0;
right=0;
}
} a[30];
int p[30],pn;
bool vis[30];
int w[30],sum;
void dfs(int x,int num)
{
vis[x]=true;
for (int i=1;i<=26;i++)
if (p[i]==1&&map[i][x]&&vis[i]==false)
{
return;//在叠这个之前还有需要叠的就退出
}
if (num==pn+1)
{
for (int j=1;j<=pn;j++) printf("%c",w[j]+'A'-1);
printf("\n");
return;
}
for (int j=1;j<=26;j++)
{
if (vis[j]==1) continue;
if (!vis[j]&&p[j])//只要i没被叠过就叠(因为这个时候x已经可以叠了)
{
vis[j]=true;
w[num]=j;
dfs(j,num+1);
vis[j]=false;
}
}
vis[x]=false;
}
int main()
{
n=read();
m=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
ch=getchar();
while (ch!='.'&& (!((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')))) ch=getchar();//只要字符和'.'
s[i][j]=ch;
if (ch=='.') continue;
int xx=ch-'A'+1;
if (!p[xx]) p[xx]=1,pn++;
a[xx].left=min(a[xx].left,j);
a[xx].right=max(a[xx].right,j);
a[xx].up=min(a[xx].up,i);
a[xx].down=max(a[xx].up,i);//把上下左右四个脚的标号确定
}
for (int i=1;i<=26;i++)
{
if (!p[i]) continue;
int j;
for (j=a[i].left;j<=a[i].right;j++)
{
int xx=s[a[i].up][j]-'A'+1;
if (xx!=i&&s[a[i].up][j]!='.') map[i][xx]=1;//xx压在i之上
xx=s[a[i].down][j]-'A'+1;
if (xx!=i&&s[a[i].down][j]!='.') map[i][xx]=1;//xx压在i之上
}
for (j=a[i].up;j<=a[i].down;j++)
{
int xx=s[j][a[i].left]-'A'+1;
if (xx!=i&&s[j][a[i].left]!='.') map[i][xx]=1;//xx压在i之上
xx=s[j][a[i].right]-'A'+1;
if (xx!=i&&s[j][a[i].right]!='.') map[i][xx]=1;//xx压在i之上
}
}
dfs(0,1);
return 0;
}