# include <iostream>
using namespace std;
bool map[155][155];
int w,h;
struct point
{
	int r1,r2,c1,c2;
};
point refer[50000*3];
bool used[155][155];
bool tused[155][155];
void printmap()
{
	for(int i=1;i<=w+h;i++)
	{
		for(int j=1;j<=w+h;j++) cout<<map[i][j];
		cout<<endl;
	}
}
int cmp(const void *a,const void *b)
{
	point *aa=(point *)a;
	point *bb=(point *)b;
	if(aa->r1!=bb->r1) return aa->r1-bb->r1;
	else if(aa->c1!=bb->c1) return aa->c1-bb->c1;
	else if(aa->r2!=bb->r2) return aa->r2-bb->r2;
	else return aa->c2-bb->c2;
}
void dfs(int r,int c,int &orir,int &oric,int &max,int now,int count)
{
	if(r==orir&&c==oric&&used[r][c]&&now!=2) 
	{
		if(now>max) max=now;
	}
	else if(tused[r][c]) return;
	else
	{
		used[r][c]=1;
		tused[r][c]=1;
		point temp;
		temp.r1=r;
		temp.c1=c;
		temp.r2=r-1;
		temp.c2=c;
		if(map[r][c]&&map[r-1][c]&&!bsearch(&temp,refer+1,count,sizeof(point),cmp))
			dfs(r-1,c,orir,oric,max,now+1,count);
		temp.r2=r+1;
		if(map[r][c]&&map[r+1][c]&&!bsearch(&temp,refer+1,count,sizeof(point),cmp))
			dfs(r+1,c,orir,oric,max,now+1,count);
		temp.r2=r;
		temp.c2=c-1;
		if(map[r][c]&&map[r][c-1]&&!bsearch(&temp,refer+1,count,sizeof(point),cmp))
			dfs(r,c-1,orir,oric,max,now+1,count);
		temp.c2=c+1;
		if(map[r][c]&&map[r][c+1]&&!bsearch(&temp,refer+1,count,sizeof(point),cmp))
			dfs(r,c+1,orir,oric,max,now+1,count);
		tused[r][c]=0;
	}
}
int main()
{
	int count_case=0;
	while(true)
	{
		cin>>w>>h;
		int count=0;
		if(!w&&!h) break;
		memset(map,0,sizeof(map));
		memset(used,0,sizeof(used));
		//构图
		for(int i=2;i<=h;i++)
			for(int j=h-(i-2);j<h-(i-2)+2*i-2;j++)
				map[i][j]=1;
		for(int i=h+1;i<=w;i++)
			for(int j=i-h+1;j<=i+h-1;j++)
				map[i][j]=1;
		for(int i=w+1;i<w+h;i++)
			for(int j=1-h+i;j<1-h+i+2*(w+h-1-i)+2;j++)
				map[i][j]=1;
		//录入，构造隔离点
		for(int i=1;i<=h;i++)
			for(int j=1;j<=w;j++)
			{
				char temp;
				cin>>temp;
				if(temp=='\\')
				{
					count++;
					refer[count].r1=i+j-1;
					refer[count].c1=h-i+j;
					refer[count].r2=refer[count].r1;
					refer[count].c2=refer[count].c1+1;
					count++;
					refer[count].r2=i+j-1;
					refer[count].c2=h-i+j;
					refer[count].r1=refer[count].r2;
					refer[count].c1=refer[count].c2+1;
					count++;
					refer[count].r1=i+j;
					refer[count].c1=h-i+j;
					refer[count].r2=refer[count].r1;
					refer[count].c2=refer[count].c1+1;
					count++;
					refer[count].r2=i+j;
					refer[count].c2=h-i+j;
					refer[count].r1=refer[count].r2;
					refer[count].c1=refer[count].c2+1;
				}
				else
				{
					count++;
					refer[count].r1=i+j-1;
					refer[count].c1=h-i+j;
					refer[count].r2=refer[count].r1+1;
					refer[count].c2=refer[count].c1;
					count++;
					refer[count].r2=i+j-1;
					refer[count].c2=h-i+j;
					refer[count].r1=refer[count].r2+1;
					refer[count].c1=refer[count].c2;
					count++;
					refer[count].r1=i+j-1;
					refer[count].c1=h-i+j+1;
					refer[count].r2=refer[count].r1+1;
					refer[count].c2=refer[count].c1;
					count++;
					refer[count].r2=i+j-1;
					refer[count].c2=h-i+j+1;
					refer[count].r1=refer[count].r2+1;
					refer[count].c1=refer[count].c2;
					
				}
			}
		qsort(refer+1,count,sizeof(point),cmp);
		int max=0,total=0;
		for(int i=1;i<=w+h;i++)
			for(int j=1;j<=w+h;j++)
			{
				if(!used[i][j]&&map[i][j])
				{
					int tmax=0,now=0;
					memset(tused,0,sizeof(tused));
					dfs(i,j,i,j,tmax,now,count);
					if(tmax>max) max=tmax;
					if(tmax>0) total++;
				}
			}
		cout<<"Maze #"<<++count_case<<":"<<endl;
		if(total) cout<<total<<" Cycles; the longest has length "<<max<<"."<<endl;
		else cout<<"There are no cycles."<<endl;
		cout<<endl;
	}
	return 0;
}



				


			   

• 说错了，是DFS (4134) yzhw 2009-04-02 20:22:01
• 问题找到了，w>h和w<=h的情况构图时要分开讨论。。附AC代码 (4172) yzhw 2009-04-03 14:07:41
  • 我是直接暴力DFS搜索AC的，大牛你这代码没看懂，谁能简单解释一下不，想知道这题如何构图 (3542) hujk2008 2012-09-18 14:50:42