Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

说错了,是DFS

Posted by yzhw at 2009-04-02 20:22:01 on Problem 1103
In Reply To:WA的不行了,用BFS做的,测试N组数据没问题。。大家帮帮忙好吗? Posted by:yzhw at 2009-04-02 20:21:45
> # 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;
> }
> 
> 
> 
> 				
> 
> 
> 			   

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator