前言

這道題和上一題（追查壞牛奶）一樣——非常超級無敵惡心難做QAQ！（其實是自己太弱）

從早上9點開始碼代碼、下午3點半開始交題到晚上AC...我現在已經神志恍惚...

很有趣的是，有一個資料長得很清奇，就像在你debug正心力憔悴的時候對你——豎了個中指（小别緻長得真東西）

【字元串-拓撲or爆搜】USA4.4——重疊的圖像Frame Up前言題目題目大意分析最開始的玄學WA代碼來之不易的AC代碼總結

題目

題目描述

看下面的五張 9 x 8 的圖像：

........   ........   ........   ........   .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 張在最頂端。如果一張圖像覆寫了另外一張圖像，那麼底下的圖像的一部分就變得不可見了。我們得到下面的圖像：

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

對于這樣一張圖像，計算構成這張圖像的矩形圖像從底部到頂端堆疊的順序。

下面是這道題目的規則：

矩形的邊的寬度為 1 ，每條邊的長度都不小于 3 。

矩形的每條邊中，至少有一部分是可見的。注意，一個角同時屬于兩條邊。

矩形用大寫字母表示，并且每個矩形的表示符号都不相同。

輸入格式

第一行兩個用空格分開的整數：圖像高 H (3 <= H <=30) 和圖像寬 W (3 <= W <= 30) 。

第二行到第 H+1 行 H 行，每行 W 個字母。

輸出格式

按照自底向上的順序輸出字母。如果有不止一種情況，按照字典順序輸出每一種情況（至少會有一種合法的順序）。

輸入輸出樣例

輸入

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

輸出

EDABC

說明/提示

題目翻譯來自NOCOW。

USACO Training Section 4.4

題目大意

有一堆中空的矩形框框，一個框框由一種大寫字母構成且一種字母隻出現一次，

框框寬為1，邊長至少為3，把他們任意疊放在一起

求從底層至最上層的框框順序，有多個答案就按字典序輸出

分析

要認真讀題啊！最開始沒看到：

【矩形的每條邊中，至少有一部分是可見的。注意，一個角同時屬于兩條邊】這個資訊，

于是毫無思路，甚至懷疑此題是否可做qwq...

首先，因為“一個角同時屬于兩條邊”，于是我們儲存每個矩形的左上角坐标與右下角坐标，就确定了整個矩形

然後，可以容易看出，最上層的矩形是完整的，于是它可以作為我們的突破口

（一）從上層往底層，逐層搜尋完整的矩形

1.按字元從大到小搜尋矩形

Ps.因為答案要求字典序，是按底層到上層從小到大的，我是從上層到底層，是以要從大到小

2.當該矩形隻含' . '或該矩形的字母時，就是合法的

3.若矩形合法，就将其字元記錄下來（我的做法是放入棧裡），然後全部變成'.'，意思是删除該矩形

4.回溯：将當層删去的矩形恢複成删前的樣子，注意不是恢複成輸入時的樣子（這一條很重要，影響到答案的正确性！）

（二）輸出答案

1.将所有答案按字典序排序

2.快樂輸出

（三）其他

1.對于多個字元串進行字典序排序的方法

因為習慣用char來搞字元串，于是從某個地方學到了qsort的玄學操作（詳見上面WA代碼），似乎是關于指針，還挺好用，隻是要背一背打法

後來請求某Tao大佬時學到了：原來string特别好用，可以直接sort，連cmp都不用打，厲害了

2.關于 char 和 string 的各種玄學

AC代碼的前身——全部用string，結果答案出現了許多奇怪的字元

AC代碼——ans[ ]，a[ ][ ]用的char，其餘string

我覺得應該是 string 與 char 直接使用a[ i ][ j ]這種單個字元時有些差別，得注意一下

最開始的玄學WA代碼

/*
ID:lunasmi2
TASK:frameup
LANG:C++                 
*/
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=50,INF=0x3f3f3f3f;
int dir1[4]={1,0,-1,0},dir2[4]={0,1,0,-1};
bool vis[MAXN+5],ok[MAXN+5];
char a[MAXN+5][MAXN+5],c[MAXN+5],ans[MAXN+5],tmp[MAXN+5],Ans[100000+5][MAXN+5];
int h,w,cnt,cnt_ans;
struct node
{
	int x1,y1,x2,y2;
}t[MAXN+5];
bool cmp(int a,int b)
{
	return a>b;
}
int CMP(const void *a,const void *b)
{
	char *s1=(char *)a;
	char *s2=(char *)b;
	return strcmp(s1,s2);
}
void print()//debug用，可忽略
{
	for(int i=1;i<=h;i++)
		printf("%s\n",a[i]+1);
	printf("\n--------------\n");
}
bool dfs(int x,int y,int C,int d)
{
	if(x==t[C].x1&&y==t[C].y1&&d==3)
	{
		a[x][y]='.';
		return true;
	}
	if(!(a[x][y]=='.'||a[x][y]-'A'==C))
		return false;
	if(x==t[C].x2&&y==t[C].y1)
	{
		if(dfs(x,y+1,C,d+1))
		{
			a[x][y]='.';
			return true;			
		}
		else
			return false;		
	}
	else if(x==t[C].x2&&y==t[C].y2)
	{
		if(dfs(x-1,y,C,d+1))
		{
			a[x][y]='.';
			return true;
		}
		else
			return false;		
	}
	else if(x==t[C].x1&&y==t[C].y2)
	{
		if(dfs(x,y-1,C,d+1))
		{
			a[x][y]='.';
			return true;
		}
		else
			return false;		
	}
	else
	{
		if(dfs(x+dir1[d],y+dir2[d],C,d))
		{
			a[x][y]='.';
			return true;
		}
		else
			return false;
	}
}
void restore(int x,int y,int C,int d)
{
	a[x][y]=C+'A';
	if(x==t[C].x1&&y==t[C].y1&&d==3)
		return;
	if(x==t[C].x2&&y==t[C].y1)
		restore(x,y+1,C,d+1);
	else if(x==t[C].x2&&y==t[C].y2)
		restore(x-1,y,C,d+1);
	else if(x==t[C].x1&&y==t[C].y2)
		restore(x,y-1,C,d+1);
	else
		restore(x+dir1[d],y+dir2[d],C,d);
}
void DFS(int id,int tot)
{
	if(tot==cnt)
	{
		for(int i=tot-1;i>=0;i--)
			tmp[(tot-1)-i]=ans[i];
		memcpy(Ans[cnt_ans++],tmp,sizeof(tmp));
		return ;
	}
	for(int i=1;i<=cnt;i++)
	{
		if(!ok[i])
		{
			if(dfs(t[c[i]].x1,t[c[i]].y1,c[i],0))
			{
				ok[i]=1;
				ans[tot]=c[i]+'A';
				DFS(i,tot+1);
				restore(t[c[i]].x1,t[c[i]].y1,c[i],0);
				ok[i]=0;
			}
		}		
	}
}
int main()
{
    //freopen("frameup.in","r",stdin);
    //freopen("frameup.out","w",stdout);
    scanf("%d%d",&h,&w);
    for(int i=0;i<26;i++)
    	t[i].x1=t[i].y1=INF,t[i].x2=t[i].y2=0;
    for(int i=1;i<=h;i++)
    {
    	scanf("%s",a[i]+1);
    	for(int j=1;j<=w;j++)
    	if(a[i][j]!='.')
    	{
    		int tmp=a[i][j]-'A';
    		if(i<t[tmp].x1||j<t[tmp].y1)
    			t[tmp].x1=min(t[tmp].x1,i),t[tmp].y1=min(t[tmp].y1,j);
    		if(i>t[tmp].x2||j>t[tmp].y2)
    			t[tmp].x2=max(t[tmp].x2,i),t[tmp].y2=max(t[tmp].y2,j);
    		if(!vis[tmp])
    		{
    			vis[tmp]=1;
    			c[++cnt]=tmp;
			}
		}
	} 
	sort(c+1,c+cnt+1,cmp);
	DFS(-1,0);
	qsort(Ans,cnt_ans,sizeof(char)*55,CMP);
	for(int i=0;i<cnt_ans;i++)
		printf("%s\n",Ans[i]);
	return 0;
}
/*
5 7 
AAA.CCC 
A.A.C.C 
AABBBCC 
..B.B.. 
..BBB.. 
-------
4 4
CCC.
CACA
CCCA
.AAA
--------
4 8
CCC..BBB
C.CAABAB
C.CA.BBB
CCCAAAAA
--------
4 8
CCC..BBB
C.C..B.B
C.C..BBB
CCC.....
--------
*/

來之不易的AC代碼

/*
ID:lunasmi2
TASK:frameup
LANG:C++                 
*/
#include<cstdio>
#include<cmath>
#include<stack>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=50,INF=0x3f3f3f3f;
int dir1[4]={1,0,-1,0},dir2[4]={0,1,0,-1};
bool vis[MAXN+5],ok[MAXN+5];
char ans[MAXN+5],a[MAXN+5][MAXN+5];
int c[MAXN+5];//記錄第i個矩形的字母(ascll碼) 
int h,w,cnt;
vector<string> Ans;//記錄最終答案并用來排字典序 
stack<char> base;//儲存舊圖資訊，友善回溯 
struct node
{
	int x1,y1,x2,y2;
}t[MAXN+5];
bool cmp(int a,int b)
{
	return a>b;
}
bool dfs(int x,int y,int C,int d)//檢查是否是完整的矩形框，若是則全部變成'.' 
{
	if(!(a[x][y]=='.'||a[x][y]-'A'==C))//'.'和屬于該矩形的字母都做合法字元 
		return false;
        //以下是走到四個矩形角上的點和一般點的情況 
	if(x==t[C].x1&&y==t[C].y1&&d==3)
	{
		base.push(a[x][y]),a[x][y],a[x][y]='.';
		return true;
	}
	if(x==t[C].x2&&y==t[C].y1)
	{//如果搜到最後矩形合法，則存下目前字元(回溯要用)，目前字元變為'.'，即删去該矩形
                if(dfs(x,y+1,C,d+1))
		{
			base.push(a[x][y]),a[x][y],a[x][y]='.';
			return true;			
		}
		else
			return false;		
	}
	else if(x==t[C].x2&&y==t[C].y2)
	{
		if(dfs(x-1,y,C,d+1))
		{
			base.push(a[x][y]),a[x][y],a[x][y]='.';
			return true;
		}
		else
			return false;		
	}
	else if(x==t[C].x1&&y==t[C].y2)
	{
		if(dfs(x,y-1,C,d+1))
		{
			base.push(a[x][y]),a[x][y],a[x][y]='.';
			return true;
		}
		else
			return false;		
	}
	else
	{
		if(dfs(x+dir1[d],y+dir2[d],C,d))
		{
			base.push(a[x][y]),a[x][y],a[x][y]='.';
			return true;
		}
		else
			return false;
	}
}
void restore(int x,int y,int C,int d)
{
	//base是逆時針存的，現在順時針将沿途字元變為彈出的字元，恢複為舊圖  
	a[x][y]=base.top();base.pop();
	if(x==t[C].x1&&y==t[C].y1&&d==3)
		return;
	if(x==t[C].x2&&y==t[C].y1)
		restore(x,y+1,C,d+1);
	else if(x==t[C].x2&&y==t[C].y2)
		restore(x-1,y,C,d+1);
	else if(x==t[C].x1&&y==t[C].y2)
		restore(x,y-1,C,d+1);
	else
		restore(x+dir1[d],y+dir2[d],C,d);
}
void DFS(int id,int tot)
{
	if(tot==cnt)
	{
		string tmp;
		for(int i=tot-1;i>=0;i--)//因為是從上層往底層搜尋的，是以倒着存答案 
			tmp+=ans[i];
		Ans.push_back(tmp);
		tmp.clear();
		return ;
	}
	for(int i=1;i<=cnt;i++)
	{
		if(!ok[i])
		{
			if(dfs(t[c[i]].x1,t[c[i]].y1,c[i],0))
			{
				ok[i]=1;
				ans[tot]=c[i]+'A';
				DFS(i,tot+1);
				restore(t[c[i]].x1,t[c[i]].y1,c[i],0);//恢複删去的矩形 
				ok[i]=0;
			}
		}		
	}
}
int main()
{
    //freopen("frameup.in","r",stdin);
    //freopen("frameup.out","w",stdout);
    cin>>h>>w;
    for(int i=0;i<50;i++)
    	t[i].x1=t[i].y1=INF,t[i].x2=t[i].y2=0;
    for(int i=0;i<h;i++)
    {
    	scanf("%s",a[i]);
    	for(int j=0;j<w;j++)
	    if(a[i][j]!='.')
	    {
	    	int tmp=a[i][j]-'A';
	    	t[tmp].x1=min(t[tmp].x1,i);
			t[tmp].y1=min(t[tmp].y1,j);
	    	t[tmp].x2=max(t[tmp].x2,i);
			t[tmp].y2=max(t[tmp].y2,j);
	    	if(!vis[tmp])
	    	{
	    		vis[tmp]=1;
	    		c[++cnt]=tmp;
			}
		}    	
	} 
	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]<<endl;
	return 0;
}

總結

1.學到了【對于多個字元串進行字典序排序的方法】

2.思維不夠全面，最開始有點偷懶..._(:зゝ∠)_...

回溯時直接把矩陣變成該矩陣的字母，以為不會有問題，結果出錯了，調了好久qwq...

多虧某Tao大佬找到了hack資料，我才終于得以AC...pwp...

【字元串-拓撲or爆搜】USA4.4——重疊的圖像Frame Up前言題目題目大意分析最開始的玄學WA代碼來之不易的AC代碼總結

【字元串-拓撲or爆搜】USA4.4——重疊的圖像Frame Up前言題目題目大意分析最開始的玄學WA代碼來之不易的AC代碼總結

前言

題目

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

題目大意

分析

最開始的玄學WA代碼

來之不易的AC代碼

總結

繼續閱讀

淺談MFC CSting類拼接效率

LR中檢查點函數簡析

C和java中關于字元串與字元數組的定義和轉化

Java：String類字元串與數組之間的轉換

Java中 byte[] 數組與 String 字元串的轉化

invalid byte 1 of 1-byte UTF-8 sequence

轉詳解C#資料庫存取圖檔三大方式

C/C++頭檔案、函數使用說明

PAT (Top Level) Practise 1019 Separate the Animals (35)

回文樹學習小結

java 日期總結

C#多線程——前台線程和背景線程

查找檔案中的字元串

QName是什麼

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

GridView終極用法(一)