Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
说错了,是DFSIn 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator