为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/frameup
来自NOCOW
< USACO
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .4中的OI题目Frame Up的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
[编辑] 方法 拓扑排序
由题意可知，不存在一个矩形的一条边被完全覆盖，所以我们可以计算出矩形的坐标。 读入时记录矩形的每个点中最小x1，最小y1，最大x2，最大y2。可知左上角 (x1,y1) 右下角 (x2,y2) 右上角 (x2,y1) 左下角 (x1,y2)。
查找该矩形A边上，非该矩形的字母B，即覆盖矩形A被矩形B覆盖。建立一条有向边B->A，表示B是A的必要条件。然后进行拓扑排序，搜索求所有的拓扑序列，并排序输出。
注意，该题中的字母可能不连续，不要直接for(i='A';i<='Z';i++)。
[编辑] 方法 字符串处理
每次找到一个完全框（也就是这个框的所有字母都可见，要么是原来的字母，要么是’*’，’*’是后面用到的临时标记），拿掉，把框上的所有字母都标记为’*’。重复上述过程直到所有框都被拿掉。 因为要求输出所有答案，所以用dfs来寻找所有解
