回溯法

POJ1128总结

Frame Stacking

Description

Consider the following 5 picture frames placed on an 9 x 8 array.


........ ........ ........ ........ .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

Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.

Viewing the stack of 5 frames we see the following.


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

In what order are the frames stacked from bottom to top? The answer is EDABC.

Your problem is to determine the order in which the frames are stacked from bottom to top given a picture of the stacked frames. Here are the rules:

1. The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters.

2. It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.

3. The frames will be lettered with capital letters, and no two frames will be assigned the same letter.

Input

Each input block contains the height, h (h<=30) on the first line and the width w (w<=30) on the second. A picture of the stacked frames is then given as h strings with w characters each.
Your input may contain multiple blocks of the format described above, without any blank lines in between. All blocks in the input must be processed sequentially.

Output

Write the solution to the standard output. Give the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities in alphabetical order, each one on a separate line. There will always be at least one legal ordering for each input block. List the output for all blocks in the input sequentially, without any blank lines (not even between blocks).

Sample Input

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

Sample Output

EDABC

第一次通过的代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;//h为高度,w为宽度,num为所用的字母个数,ans_num为答案个数 
int flag[26]={0};//标记'A'+i号字母是否被用 
struct alphbet
//这个是每一个字母的信息 
{
	char alph;//记录字母 
	int top,bot,left,right;//记录这个字母框的上下左右的坐标 
}list[26];
struct answer
//记录所有答案,为了排序 
{
	char alph[26];
}ans[40320];
char picture[31][31];//记录图片
//对答案排序 
bool cmp(answer a,answer b)
{
	if (strcmp(a.alph,b.alph)<0) return 1;
	else return 0;
}
//找框架的上界坐标 
int seektop(char c)
{
	for (int i=0;i<h;i++)
	{
		for (int j=0;j<w;j++)
		{
			if (picture[i][j]==c) return i;
		}
	}
}
//找框架的下界坐标 
int seekbot(char c)
{
	for (int i=h-1;i>=0;i--)
	{
		for (int j=0;j<w;j++)
		{
			if (picture[i][j]==c) return i;
		}
	}
}
//找框架的左界坐标 
int seekleft(char c)
{
	for (int i=0;i<w;i++)
	{
		for (int j=0;j<h;j++)
		{
			if (picture[j][i]==c) return i;
		}
	}
}
//找框架的右界坐标 
int seekright(char c)
{
	for (int i=w-1;i>=0;i--)
	{
		for (int j=0;j<h;j++)
		{
			if (picture[j][i]==c) return i;
		}
	}
}
//判断这个字母是否被其它字母挡住 
int check(int c)
{
	for (int i=list[c].left;i<=list[c].right;i++)
	{
		if (picture[list[c].top][i]!=list[c].alph&&picture[list[c].top][i]!='.') return 0;
		if (picture[list[c].bot][i]!=list[c].alph&&picture[list[c].bot][i]!='.') return 0;
	}
	for (int i=list[c].top;i<=list[c].bot;i++)
	{
		if (picture[i][list[c].left]!=list[c].alph&&picture[i][list[c].left]!='.') return 0;
		if (picture[i][list[c].right]!=list[c].alph&&picture[i][list[c].right]!='.') return 0;
	}
	return 1;
}
int dfs(int n,int t)
{
	if (t==n+1) 
	//递归出口,将答案存储进结构体中 
	{
		ans[ans_num].alph[n]='\0';
		strcpy(ans[ans_num+1].alph,ans[ans_num].alph);
		ans_num++;
		return 1;
	}
	else
	{
		for (int i=0;i<n;i++)
		{
			if (flag[list[i].alph-'A'])
			//如果该字母被使用 
			{
				if (check(i))
				//如果这个字母没被挡住 
				{
					//将这个字母框架从图中拆了 
					for (int j=list[i].left;j<=list[i].right;j++)
					{
						picture[list[i].top][j]='.';
						picture[list[i].bot][j]='.';
					}
					for (int j=list[i].top;j<=list[i].bot;j++)
					{
						picture[j][list[i].left]='.';
						picture[j][list[i].right]='.';
					}
					//因为暂时被拆了,所以图上暂时没有这个字母	
					flag[list[i].alph-'A']=0;
					//将这个字母存到答案序列中 
					ans[ans_num].alph[n-t]=list[i].alph;
					//递归下一个 
					dfs(n,t+1);
					//回溯,把这个框架装上去 
					flag[list[i].alph-'A']=1;
					for (int j=list[i].left;j<=list[i].right;j++)
					{
						picture[list[i].top][j]=list[i].alph;
						picture[list[i].bot][j]=list[i].alph;
					}
					for (int j=list[i].top;j<=list[i].bot;j++)
					{
						picture[j][list[i].left]=list[i].alph;
						picture[j][list[i].right]=list[i].alph;
					}
				}
			}
		}
	}
}
int main()
{
	char c;
	while (scanf("%d%d",&h,&w)==2)
	{
		num=0;
		ans_num=0;
		for (int i=0;i<26;i++)
		{
			flag[i]=0;
		}
		for (int i=0;i<h;i++)
		{
			c=getchar();
			for (int j=0;j<w;j++)
			{
				scanf("%c",&picture[i][j]);
				if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
			}
		}
		for (int i=0;i<26;i++)
		{
			if (flag[i]) 
			//如果一个字母被使用,就将其加入到list中,并且寻找其框架的边界位置 
			{
				list[num].alph=(char)('A'+i);
				list[num].top=seektop((char)('A'+i));
				list[num].bot=seekbot((char)('A'+i));
				list[num].left=seekleft((char)('A'+i));
				list[num].right=seekright((char)('A'+i));
				num++;
			}
		}
		dfs(num,1);
		//排序 
		sort(ans,(ans+ans_num),cmp);
		for (int i=0;i<ans_num;i++)
		{
			for (int j=0;j<num;j++) 
			printf("%c",ans[i].alph[j]);
			printf ("\n");
		}
	}
	return 0;
}

第一次做这个题目时,我的想法是,这道题可以搜索最上层的框架,将其拆掉之后就能拆下面的框架了。一个框架被拆除时,将其框架所在的位置全部赋值为’.’;一个框架如果是在最上层,当且仅当在其框架范围内只有自身和符号’.’(其上层被拆下之后的痕迹);回溯时将这个框架再安装上去,即所在位置赋值为自身。

根据我自己已经有的经验,一般搜索题的递归函数内容不会很复杂,因为往往在正式递归之前可以将题目转化为另外的模型,例如图论等等。于是上网寻找解法,发现清一色都是利用拓扑排序

第二次通过的代码 拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

执行步骤

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之;
(2) 从网中删除此顶点及所有出边。

循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。

本题思路:

先根据图片来构造图,然后递归地进行拓扑排序。

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int h,w,num,ans_num;
int flag[26]={0};
int have[26][26]={0};//have[i][j]记录j是否在i的上方,即j是否是i的先行节点 
char picture[31][31];
char temp[26];//记录当前的答案 
int map[26][26];//构造有向无环图 
struct alphbet
{
	char alph;
	int top,bot,left,right;
	int in;//记录入度 
	char fore[16];//记录先行节点 
	alphbet(){in=0;}
}list[26];
struct answer
{
	char alph[26];
}ans[40320];
bool cmp(answer a,answer b)
{
	if (strcmp(a.alph,b.alph)<0) return 1;
	else return 0;
}
int seektop(char c)
{
	for (int i=0;i<h;i++)
	{
		for (int j=0;j<w;j++)
		{
			if (picture[i][j]==c) return i;
		}
	}
}
int seekbot(char c)
{
	for (int i=h-1;i>=0;i--)
	{
		for (int j=0;j<w;j++)
		{
			if (picture[i][j]==c) return i;
		}
	}
}
int seekleft(char c)
{
	for (int i=0;i<w;i++)
	{
		for (int j=0;j<h;j++)
		{
			if (picture[j][i]==c) return i;
		}
	}
}
int seekright(char c)
{
	for (int i=w-1;i>=0;i--)
	{
		for (int j=0;j<h;j++)
		{
			if (picture[j][i]==c) return i;
		}
	}
}
//构造有向无环图 
void buildmap()
{	
	for (int i=0;i<num;i++)
	{
		if (flag[list[i].alph-'A'])
		{
			//寻找自己的框架上有哪些其它的字母,这些字母就是这个框架的先行字母 
			for (int j=list[i].top;j<=list[i].bot;j++)
			{
				if (picture[j][list[i].left]!='.'&&picture[j][list[i].left]!=list[i].alph)
				{have[list[i].alph-'A'][picture[j][list[i].left]-'A']=1;}
				if (picture[j][list[i].right]!='.'&&picture[j][list[i].right]!=list[i].alph)
				{have[list[i].alph-'A'][picture[j][list[i].right]-'A']=1;}
			}
			for (int j=list[i].left;j<=list[i].right;j++)
			{
				if (picture[list[i].top][j]!='.'&&picture[list[i].top][j]!=list[i].alph)
				{have[list[i].alph-'A'][picture[list[i].top][j]-'A']=1;}
				if (picture[list[i].bot][j]!='.'&&picture[list[i].bot][j]!=list[i].alph)
				{have[list[i].alph-'A'][picture[list[i].bot][j]-'A']=1;}
			}
			for (int j=0;j<26;j++)
			{
				if (have[list[i].alph-'A'][j])
				{
					list[i].fore[list[i].in++]=(char)(j+'A');
				}
			}
		}
	}
}
void topoSort(int u,int t)
{
	temp[t]=list[u].alph;
	if (t==num)
	//递归出口将答案赋值给结构体 
	{
		for (int i=1;i<=num;i++) ans[ans_num].alph[i-1]=temp[num-i+1];
		ans[ans_num].alph[num]='\0';
		ans_num++;
		return;
	}
	else
	{
		//拆掉这个框架
		//这个框架下的所有框架入度减一 
		for (int i=0;i<26;i++)
		{
			if (have[i][u])	list[i].in--;
		}
		//将其入度标为-1 
		list[u].in=-1;
		//寻找下一个入度为0的字母 
		for (int i=0;i<num;i++)
		{
			if (list[i].in==0)	topoSort(i,t+1);
		}
		//回溯 
		for (int i=0;i<26;i++)
		{
			if (have[i][u])	list[i].in++;
		}
		list[u].in=0;
	}	
}
int main()
{
	char c;
	while (scanf("%d%d",&h,&w)==2)
	{
		num=0;
		ans_num=0;
		memset(flag,0,sizeof(flag));
		memset(map,0,sizeof(map));
		memset(have,0,sizeof(have));
		for (int i=0;i<h;i++)
		{
			c=getchar();
			for (int j=0;j<w;j++)
			{
				scanf("%c",&picture[i][j]);
				if (picture[i][j]!='.')	flag[picture[i][j]-'A']=1;
			}
		}
		for (int i=0;i<26;i++)
		{
			if (flag[i]) 
			{
				list[num].alph=(char)('A'+i);
				list[num].top=seektop((char)('A'+i));
				list[num].bot=seekbot((char)('A'+i));
				list[num].left=seekleft((char)('A'+i));
				list[num].right=seekright((char)('A'+i));
				num++;
			}
		}
		buildmap();
		
		for (int i=0;i<num;i++)
		{
			if (list[i].in==0)	topoSort(i,1);
		}
		sort(ans,(ans+ans_num),cmp);
		for (int i=0;i<ans_num;i++)
		{
			for (int j=0;j<num;j++) 
			printf("%c",ans[i].alph[j]);
			printf ("\n");
		}
		for (int i=0;i<num;i++)
		{
			for (int j=0;j<list[i].in;j++);
			
			list[i].in=0;
		}
	}
	return 0;
}

反思

网上说这道题不用对答案进行排序,可是我想了一通找不到不用排序的方法。另外第二种做法反而比第一种做法代码更长,确实让人无语。

对于字符串数组(二位字符数组),不能直接用sort排序,需要将字符串存入到结构体中,再使用sort排序。

struct answer
//记录所有答案,为了排序 
{
	char alph[26];
}ans[40320];
char picture[31][31];//记录图片
//对答案排序 
bool cmp(answer a,answer b)
{
	if (strcmp(a.alph,b.alph)<0) return 1;
	else return 0;
}

发表评论