题解 P2741 【[USACO4.4]重叠的图像Frame Up】
非常开心的用暴力过了这题……
虽说是暴力，还是要一点优化（剪枝）
首先是处理字符的问题。我用bool bExisted[26]表示这个字符是否出现过。（其中'A'的下标为0，'B'为1，以此类推）
然后我们再扫一遍bExisted给出现过的字符按照顺序分配hash值。（因为我们需要深搜，可以写for(i->26)，但我更喜欢for(i->end_of_hash)）
再然后就是处理矩形的问题，大家大概都能想到这个做法：因为这个矩形的每条边都会出现在最终图像中，所以我们可以扫描一遍图像，在相同字母中取最小的x作为矩形的left，最小的y作为矩形的top，最大的x作为矩形的right，最大的y作为矩形的bottom（这四个量分别是矩形的左、上、右、下边框）。注意，这个时候我们已经得到了每个字符的hash值，可以直接访问每个字符对应的矩形实例了。
哦对了，我们需要定义一个rect：
class rect
{
public:
rect() : left(11234), top(11234), right(-11234), bottom(-11234) {}//初始化
int left, top, right, bottom;
}all[26];//由于只有26个大写字母，它只要开26个就够了。然后就是搜索了。朴素的深搜大家都懂：枚举全排列，判断是否可行。（似乎只TLE一个点，而且O2也过不去的一个点）
优化：用cover记录每个位置要被覆盖的次数。
如下图：
AAA..
A.BBB
A.B.B
AABBB那么cover数组如下：
11100
10211
10201
11211即这个位置总共会被覆盖多少次。
这样有什么好处呢？如果当前放下去的矩形所要露出来的地方cover不等于1，那么我们现在把它放下去肯定是不合法的：因为cover不等于1，意味着这个位置还要被后来的矩形覆盖。
这样子就可以0msAC那个TLE的点了。
上代码：
#include <cstdio>
#include <cstdlib>
#include <algorithm>
inline void GetMin(int& a, int b) { if (b < a) a = b; }
inline void GetMax(int& a, int b) { if(b > a) a = b; }
class rect
{
public:
rect() : left(11234), top(11234), right(-11234), bottom(-11234) {}
int left, top, right, bottom;
}all[26];
int iEnd;
int hash[26];
char val[26];
bool bExisted[26];
int n, m;
int cover[31][31];//覆盖次数
char map[31][31];//目标状态
char buf[31][31];//搜索时的状态
char old[26][31][31];//选择前的状态（回溯时用）
bool bUsed[26];//这个矩形是否已被放置
char out[26];//存储方案
void dfs(int now)
{
if (now == iEnd)
{
printf("%s\n", out);
return;
}
for (int i(0); i != iEnd; ++i)
{
if (bUsed[i]) continue;
bool fail(false);
for (int x(all[i].left); x <= all[i].right; ++x)
{
if (map[x][all[i].top] == val[i] && cover[x][all[i].top] != 1
|| map[x][all[i].bottom] == val[i] && cover[x][all[i].bottom] != 1)
{
fail = true;//这里在通过cover数组判断这么做是否可行，原理如前文所述
break;
}
}
if (fail) continue;
for (int y(all[i].top); y <= all[i].bottom; ++y)
{
if (map[all[i].left][y] == val[i] && cover[all[i].left][y] != 1
|| map[all[i].right][y] == val[i] && cover[all[i].right][y] != 1)
{
fail = true;
break;
}
}
if (fail) continue;
bUsed[i] = true;
for (int x(all[i].left); x <= all[i].right; ++x)
{
old[now][x][all[i].top] = buf[x][all[i].top];//记录修改前将被修改的位置的状态
old[now][x][all[i].bottom] = buf[x][all[i].bottom];
}
for (int y(all[i].top); y <= all[i].bottom; ++y)
{
old[now][all[i].left][y] = buf[all[i].left][y];
old[now][all[i].right][y] = buf[all[i].right][y];
}
for (int x(all[i].left + 1); x < all[i].right; ++x)
{
buf[x][all[i].top] = val[i];//修改搜索状态
buf[x][all[i].bottom] = val[i];
--cover[x][all[i].top];//修改将被覆盖的次数
--cover[x][all[i].bottom];
}
for (int y(all[i].top); y <= all[i].bottom; ++y)
{
buf[all[i].left][y] = val[i];//如上循环，只是矩形有四条边，所以分两个循环
buf[all[i].right][y] = val[i];
--cover[all[i].left][y];
--cover[all[i].right][y];
}
out[now] = val[i];//标记方案
dfs(now + 1);
for (int x(all[i].left + 1); x < all[i].right; ++x)//回溯状态
{
buf[x][all[i].top] = old[now][x][all[i].top];
buf[x][all[i].bottom] = old[now][x][all[i].bottom];
++cover[x][all[i].top];
++cover[x][all[i].bottom];
}
for (int y(all[i].top); y <= all[i].bottom; ++y)
{
buf[all[i].left][y] = old[now][all[i].left][y];
buf[all[i].right][y] = old[now][all[i].right][y];
++cover[all[i].left][y];
++cover[all[i].right][y];
}
bUsed[i] = false;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i(0); i != n; ++i)
{
scanf("%s", map[i]);
for (int j(0); j != m; ++j)
{
if (map[i][j] != '.') bExisted[map[i][j] - 'A'] = true;//标记该字符为“存在”
buf[i][j] = '.';
}
}
for (int i(0); i != 26; ++i)//为字符分配hash值（主要是需要hash连续排列，否则可以直接取其ASCII码
{
if (bExisted[i])
{
hash[i] = iEnd;
val[iEnd++] = 'A' + i;//标记这个hash的原值
}
}
for (int i(0); i != n; ++i)//寻找矩形的边界
{
for (int j(0); j != m; ++j)
{
if (map[i][j] != '.')
{
rect& x(all[hash[map[i][j] - 'A']]);
GetMin(x.left, i);
GetMin(x.top, j);
GetMax(x.right, i);
GetMax(x.bottom, j);
}
}
}
for (int i(0); i != iEnd; ++i)
{
for (int x(all[i].left + 1); x < all[i].right; ++x)
{
++cover[x][all[i].top];//初始化cover
++cover[x][all[i].bottom];
}
for (int y(all[i].top); y <= all[i].bottom; ++y)
{
++cover[all[i].left][y];
++cover[all[i].right][y];
}
}
dfs(0);//寻找方案，输出
return 0;
}