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