usaco_4_4_3_frameup.cpp

usaco自己做的1到5章的代码

/*
这道题可以直接搜索，dfs即可。
另外，还可以用拓扑排序来做。
我是直接模拟搜索的，题目中一个条件很重要，那就是每个矩形的每条边都至少有一个字母可以看见(转角算两条边的)
这样，搜索一遍就能得到整幅图中各个字母矩形的左上坐标和右下坐标
然后搜索，每次找到没被覆盖的矩形，把它的边上所有的点标记为*，然后搜下一层
这样，每搜出一个结果，存入ans数组，最后对ans排序输出即可！
注意，ans数字要开到10000左右才能过！
刚开始把搜索矩形坐标放在了dfs函数的循环体呢，搞超时了~~提交四次才过……
*/
/*
PROB: frameup
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<string>
#include<algorithm>
#define cin fin
using namespace std;
char map[30][30];
bool used[26];
int n,m,charnum=0,ansn;
char s[26],ys[26];
int xa[26],ya[26],xb[26],yb[26];
string ans[10000];
void dfs(int);
void printans();
ifstream fin("frameup.in");
ofstream fout("frameup.out");
void calcxy()
{
 	int i,j,k,t,c=0;
	bool check[26];
	memset(check,false,sizeof(check));
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			int x1=-1,y1=-1,x2=-1,y2=-1;
			if(check[map[i][j]-'A'] || map[i][j]=='.') continue;
			check[map[i][j]-'A']=true;
			for(k=0;k<n;k++){
			    if(x1>-1) break;
				for(t=0;t<m;t++)
					if(map[k][t]==map[i][j]) {x1=k;break;}
			}
			for(k=n-1;k>=0;k--){
			    if(x2>-1) break;
				for(t=0;t<m;t++)
					if(map[k][t]==map[i][j]) {x2=k;break;}
			}
			for(t=0;t<m;t++){
			    if(y1>-1) break;
				for(k=0;k<n;k++)
					if(map[k][t]==map[i][j]) {y1=t;break;}
			}
			for(t=m-1;t>=0;t--){
			    if(y2>-1) break;
				for(k=0;k<n;k++)
					if(map[k][t]==map[i][j]) {y2=t;break;}
			}
			for(k=0;k<charnum;k++) if(ys[k]==map[i][j]) break;
			xa[k]=x1; 
			xb[k]=x2;
			ya[k]=y1;
			yb[k]=y2;
		}
}
int main()
{
	int i,j,k;
	cin>>n>>m;
	charnum=0;
	memset(used,false,sizeof(used));
	fin.get();
	for(i=0;i<n;i++){
		for (j=0;j<m;j++)
		{
			fin.get(map[i][j]);
			if(!used[map[i][j]-'A'] && map[i][j]!='.') 
				{used[map[i][j]-'A']=true; ys[charnum]=map[i][j]; charnum++;}
		}
		fin.get();
	}
	sort(ys,ys+charnum);
	memset(used,false,sizeof(used));
	calcxy();
	dfs(0);
	printans();
//	system("pause");
	return 0;

}
void printans()
{
	int i;
	for(i=0;i<ansn;i++)  reverse(ans[i].begin(),ans[i].end());
	sort(ans,ans+ansn);
	for(i=0;i<ansn;i++)  
        fout<<ans[i]<<endl;
}
void dfs(int dep)
{
	int i,j,k,t;
	char ji[30][30];
	memcpy(ji,map,sizeof(map));
	if (dep==charnum)
	{
		s[dep]='\0';
		ans[ansn++].assign(s);
		return;
	}
	for(i=0;i<charnum;i++)
	{
		if(used[i]) continue;
		int x1=xa[i];
		int x2=xb[i];
		int y1=ya[i];
		int y2=yb[i];
		bool yes=true;
		for(k=y1;k<=y2;k++) if(ji[x1][k]!=ys[i]&&ji[x1][k]!='.')
                {yes=false; break;}
        for(k=y1;k<=y2;k++) if(ji[x2][k]!=ys[i]&&ji[x2][k]!='.')
                {yes=false; break;}
        for(k=x1;k<=x2;k++) if(ji[k][y1]!=ys[i]&&ji[k][y1]!='.')
                {yes=false; break;}
        for(k=x1;k<=x2;k++) if(ji[k][y2]!=ys[i]&&ji[k][y2]!='.')
                {yes=false; break;}
        if(!yes) continue;  
		used[i]=true;
        s[dep]=ys[i];
        for(k=x1;k<=x2;k++) {map[k][y1]='.'; map[k][y2]='.';}
        for(k=y1;k<=y2;k++) {map[x1][k]='.'; map[x2][k]='.';}
        dfs(dep+1);
		used[i]=false;
		memcpy(map,ji,sizeof(ji));
	}
}