题解 P2741 【[USACO4.4]重叠的图像Frame Up】
VectorMF
·
·
题解
题目由此去
一道非常恶心的题目（
以上为感受
题目大意：
$2.$ 这些框宽为$1$，每条边的长度都至少$3$。
$3.$ 求从底层至最上层的框顺序，有多个答案就按字典序输出
------------
### 分析:
再看分析之前要先保证回$string$和$char$的一些用法。
$First.$因为
“${\color{red}\colorbox{blue}{一个角同时属于两条边}}$”，于是我们保存每个矩形的左上角坐标与右下角坐标，就确定了整个矩形。
$Next.$可以看出，最上层的矩形是完整的，于是它可以作为本题突破口。
（一）从上层往底层，逐层搜索完整的矩形
$1.$ 按字符从大到小搜索矩形
$2.$ 当该矩形只含 “ . ” $or$ 该矩形的字母时，就是符合题意的。
$3.$ 若矩形符合题意，就将其字符放入栈中，然后全部变成 “ . ” ， 删除该矩形
$4.$ ${\color{red}DFS}$：将当层删去的矩形恢复成删前的样子，注意不是恢复成输入时的样子。
------------
上代码：
```
#include <bits/stdc++.h>
using namespace std;
const int MAXX = 35;
const int INF = 0x7fffffff/2;
struct Nice {
int x1 , y1 , x2 , y2;
}tc[MAXX];
int h , w , cnt , cntans;
char g[MAXX][MAXX] , c[MAXX] , ans[MAXX] , Ans[MAXX * MAXX][MAXX] , tp[MAXX];
bool v[MAXX] , flag[MAXX];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1};
bool cmp(int a , int b) {
return a > b;
}
int Cmp(const void *a , const void *b) {
char *s1 = (char *)a , *s2 = (char *)b;
return strcmp(s1 , s2);
}
bool dfs(int x , int y , int xx , int yy) {
if (x == tc[xx].x1 && y == tc[xx].y1 && yy == 3) {
g[x][y] = '.';
return 1;
}
if (!(g[x][y] == '.' || g[x][y] - 'A' == xx)) {
return 0;
}
if (x == tc[xx].x2 && y == tc[xx].y1 ) {
if (dfs(x , y + 1 , xx , yy + 1)) {
g[x][y] = '.';
return 1;
}
else return 0;
}
else if (x == tc[xx].x2 && y == tc[xx].y2 ) {
if (dfs(x - 1 , y , xx , yy + 1)) {
g[x][y] = '.';
return 1;
}
else return 0;
}
else if (x == tc[xx].x1 && y == tc[xx].y2 ) {
if (dfs(x , y - 1 , xx , yy + 1)) {
g[x][y] = '.';
return 1;
}
else return 0;
}
else {
if (dfs(x + dx[yy] , y + dy[yy] , xx , yy)) {
g[x][y] = '.';
return 1;
}
else return 0;
}
}
void work(int x , int y , int xx , int yy) {
g[x][y] = xx + 'A';
if(x == tc[xx].x1 && y == tc[xx].y1 && yy == 3) {
return;
}
if(x == tc[xx].x2 && y == tc[xx].y1) {
work(x , y + 1 , xx , yy+1);
}
else if(x == tc[xx].x2 && y == tc[xx].y2) {
work(x - 1 , y , xx , yy + 1);
}
else if(x == tc[xx].x1 && y == tc[xx].y2) {
work(x , y - 1 , xx , yy + 1);
}
else {
work(x + dx[yy] , y + dy[yy] , xx , yy);
}
}
void DFS(int xi , int yi) {
if (yi == cnt) {
for (int i=yi-1; i>=0; i-- ) {
tp[yi - 1 - i] = ans[i];
}
memcpy(Ans[cntans++ ] , tp , sizeof(tp));
return ;
}
for (int i=1; i<=cnt; i++ ) {
if (!flag[i] && dfs(tc[c[i]].x1 , tc[c[i]].y1 , c[i] , 0)) {
flag[i] = 1;
ans[yi] = c[i] + 'A';
DFS(i , yi + 1);
work(tc[c[i]].x1 , tc[c[i]].y1 , c[i] , 0);
flag[i] = 0;
}
}
}
void Work() {
for (int i=1; i<=h; i++) {
scanf("%s",g[i] + 1);
for(int j=1; j<=w; j++) {
if(g[i][j] != '.') {
int kkk=g[i][j] - 'A';
if(i < tc[kkk].x1 || j < tc[kkk].y1 ) {
tc[kkk].x1 = min(tc[kkk].x1 , i);
tc[kkk].y1 = min(tc[kkk].y1 , j);
}
if(i > tc[kkk].x2 || j > tc[kkk].y2 ) {
tc[kkk].x2 = max(tc[kkk].x2 , i);
tc[kkk].y2 = max(tc[kkk].y2 , j);
}
if(!v[kkk]) {
v[kkk] = 1;
c[++cnt] = kkk;
}
}
}
}
}
int main(void ) {
scanf("%d %d",&h,&w);
for (int i=0; i<26; i++ ) {
tc[i].x1 = INF;
tc[i].y1 = INF;
tc[i].x2 = 0;
tc[i].y2 = 0;
}
Work();
sort(c + 1 , c + cnt + 1 , cmp);
DFS(-1 , 0);
qsort(Ans , cntans , sizeof(char)*55 , Cmp);
for (int i=0; i<cntans; i++ ) {
cout << Ans[i];
}
}
/*
in:
9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
out:
EDABC
*/
```
我：“AC！AC！AC！啊。。。WA*还RE。”很惨44分。
心想：RE改改就好。。。可是数组开大了RE的点又变成WA。。。
So!改！
经过思考：貌似要vector和stack。
额。。。在150多行的代码中加vector和stack。。。可海星。
中途对小号私信发泄。。。~~内容为【数据删除，请自行想象|A|】~~
提出我最后的AC代码：
```cpp
//stack（堆栈） 提供了堆栈的全部功能，也就是说实现了一个先进后出的
#include <bits/stdc++.h>
#include <vector>
#include<stack>
using namespace std;
const int MAXX = 50 + 5;
const int INF = 0x3f3f3f3f;
vector<string> Ans;//记录最终答案并用来排字典序
stack<char> mx;//储存旧图信息，方便回溯
//被逼无奈才用vector和stack
struct Nice {
int x1 , y1 , x2 , y2;
}tc[MAXX];
int h , w , cnt , cntans;
char g[MAXX][MAXX] , c[MAXX] , ans[MAXX] , tp[MAXX];
bool v[MAXX] , flag[MAXX];
int dx[4] = {1 , 0 , -1 , 0} , dy[4] = {0 , 1 , 0 , -1};
bool cmp(int a , int b) {
return a > b;
}
bool dfs(int x , int y , int xx , int yy) {
if (!(g[x][y] == '.' || g[x][y] - 'A' == xx)) {
return 0;
}
if (x == tc[xx].x1 && y == tc[xx].y1 && yy == 3) {
mx.push(g[x][y]) , g[x][y] = '.';
return 1;
}
if (x == tc[xx].x2 && y == tc[xx].y1 ) {
if (dfs(x , y + 1 , xx , yy + 1)) {
mx.push(g[x][y]) , g[x][y] = '.';
return 1;
}
else return 0;
}
else if (x == tc[xx].x2 && y == tc[xx].y2 ) {
if (dfs(x - 1 , y , xx , yy + 1)) {
mx.push(g[x][y]) , g[x][y] = '.';
return 1;
}
else return 0;
}
else if (x == tc[xx].x1 && y == tc[xx].y2 ) {
if (dfs(x , y - 1 , xx , yy + 1)) {
mx.push(g[x][y]) , g[x][y] = '.';
return 1;
}
else return 0;
}
else {
if (dfs(x + dx[yy] , y + dy[yy] , xx , yy)) {
mx.push(g[x][y]) , g[x][y] = '.';
return 1;
}
else return 0;
}
}
void work(int x , int y , int xx , int yy) {
g[x][y] = mx.top();
mx.pop();
if(x == tc[xx].x1 && y == tc[xx].y1 && yy == 3) {
return;
}
if(x == tc[xx].x2 && y == tc[xx].y1) {
work(x , y + 1 , xx , yy + 1);
}
else if(x == tc[xx].x2 && y == tc[xx].y2) {
work(x - 1 , y , xx , yy + 1);
}
else if(x == tc[xx].x1 && y == tc[xx].y2) {
work(x , y - 1 , xx , yy + 1);
}
else {
work(x + dx[yy] , y + dy[yy] , xx , yy);
}
}
void DFS(int xi , int yi) {
if (yi == cnt) {
string sss;
for (int i=yi-1; i>=0; i-- ) {
sss += ans[i];
}
Ans.push_back(sss);
sss.clear();
return ;
}
for (int i=1; i<=cnt; i++ ) {
if (!flag[i]) {
if (dfs(tc[c[i]].x1 , tc[c[i]].y1 , c[i] , 0)) {
flag[i] = 1;
ans[yi] = c[i] + 'A';
DFS(i , yi + 1);
work(tc[c[i]].x1 , tc[c[i]].y1 , c[i] , 0);
flag[i] = 0;
}
}
}
}
void Work() {
for (int i=0; i<h; i++) {
scanf("%s",g[i]);
for(int j=0; j<w; j++) {
if(g[i][j] != '.') {
int kkk = g[i][j] - 'A';
tc[kkk].x1 = min(tc[kkk].x1 , i);
tc[kkk].y1 = min(tc[kkk].y1 , j);
tc[kkk].x2 = max(tc[kkk].x2 , i);
tc[kkk].y2 = max(tc[kkk].y2 , j);
if(!v[kkk]) {
v[kkk] = 1;
c[++cnt] = kkk;
}
}
}
}
}
int main() {
scanf("%d %d",&h,&w);
for (int i=0; i<50; i++ ) {
tc[i].x1 = INF;
tc[i].y1 = INF;
tc[i].x2 = 0;
tc[i].y2 = 0;
}
Work();
sort(c + 1 , c + cnt + 1 , cmp);
DFS(-1 , 0);
sort(Ans.begin(),Ans.end());
for (int i=0; i<Ans.size() ; i++ ) {
cout << Ans[i] << "\n";
}
}
/*
in:
9 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
out:
EDABC
*/
```
感觉是做复杂了。。。看来VC还是那样弱啊qwq
#### 这篇题解都到这里了，求管理给过qwq