题目链接：http://acm.ocrosoft.com/problem.php?id=1246
题目描述：
下图为5个放置在9x8 的点阵中的方框图:
若将他们按顺序叠放起来.则会有某些框的一部分盖住了另外一个框,遮住一些部分.
下图是这5个框叠放起来的图形:
那么这些方框从下至上叠放的顺序是什么呢?
答案是: EDABC.
你的任务是对于一个给定的方框叠放以后的图形, 找出他们从下至上的叠放顺序.
下面是一些规则:
(1). 方框的边宽度为一个字符,边长不少于3个字符;
(2). 每个方框的4条边都有一部分可见, 一个角代表两条边;
(3). 方框用大写字母了表示, 没有两个方框用相同的字符来表示.
输入格式
前两行每行一个数字，分别表示长、宽。
接下来为框叠起来的图。没有框的地方用'.'表示。
输出格式
输出全部可能情况。
按字典顺序排序。
样例1
样例输入1
9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
Copy 样例输出1
EDABC
思路：
首先因为每个字母矩形顶角都一定是有的，所以我们可以先求出左上和右下角两个顶角。然后就可以确定下这个矩形的形状了，然后沿着四条边扫描一遍，如果有一个字母c在当前字母k矩阵上面，那么说明c一定是在k上面的，那么肯定有在输出顺序中c要在k后面。
然后就是拓扑排序。用book[i][j]记录有向边，那么很容易就变成一个求所有拓扑序列的问题了。因为序列要从小到大字典序，而且要输出全部的情况，所以我们考虑dfs即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
char a[50][50];//存储初始方阵
char ans[50];//记录答案
int book[50][50];//记录有向路径
int in[50];//记录c字符前面有几个字符
int h[50];//记录某个字母有没有用到
int cnt;//记录方阵中有几个字母
void dfs(int cur)
{
if (cur == cnt)
{
cout << ans << endl;
}
else
{
for (int i = 0; i < 26; i++)
{
if (in[i] == 0 && h[i])//如果该字母没有前缀了且这个字母被输入过
{
ans[cur] = i + 'A';
in[i] = -1;//这个字母前面没有字母了
for (int j = 0; j < 26; j++)
{
if (book[i][j])
{
in[j]--;//所有用这个字母的前面都要少1
}
}
dfs(cur + 1);
in[i] = 0;//回溯
for (int j = 0; j < 26; j++)
{
if (book[i][j])
{
in[j]++;//所有用这个字母的前面都要加1
}
}
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (int k = 0; k < 26; k++)//26个字母遍历一遍
{
char ch = 'A' + k;//遍历的那个字母赋值给ch
int x1 = 50, y1 = 50, x2 = 0, y2 = 0;
for (int i = 1; i <= n; i++)//求出遍历的那个图案的左上角和右下角
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == ch)
{
x1 = min(x1, i), y1 = min(y1, j);
x2 = max(x2, i), y2 = max(y2, j);
}
}
}
if (x1 == 50 || y1 == 50 || x2 == 0 || y2 == 0)//保持原样说明没有这个字母，直接到下一个循环
{
continue;
}
h[k] = 1;//表示这个字母输入过
cnt++;//输入的总字母++
for (int i = x1; i <= x2; i++)
{
for (int j = y1; j <= y2; j++)
{
if (i == x1 || i == x2 || j == y1 || j == y2)
{
if (a[i][j] != ch && a[i][j] != '.')//不是k字母那就说明该字母在k字母的后面
{
int c = a[i][j] - 'A';
if (!book[k][c])
{
book[k][c] = 1;//k到c是可行的
in[c]++;//c的前面有in[c]个字母
}
}
}
}
}
}
dfs(0);
}
京公网安备 11010502036488号