The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

杭电月赛 2.6

这个搜索题折腾了我不少时间,代码跑得比较慢 效率还有提升的空间
#include<iostream>
#include
<cmath>
#include
<cstring>
using namespace std;

struct node
{
    
int x1,y1;
    
int x2,y2;
    
int time;
}
l[10000000];

int v[50][50][50][50];
int m[100][100];

void myswap(int &x,int &y)
{

    
int t=x;
    x
=y;
    y
=t;
}



int hx1,hy1;
int hx2,hy2;
char str[100];
int n,mm;//n为高m为宽

void input(int n,int mm)
{
    
int cnt=1;
    
int cnt2=1;
    
int i,j;
    
int len;
    
for(i=0;i<n;i++)
    
{

        scanf(
"%s",str);
        len
=strlen(str);
        
for(j=0;j<len;j++)
        
{
            
            
if(str[j]=='*')
                m[i][j]
=2;
            
else if(str[j]=='B')
            
{
                m[i][j]
=0;
                
if(cnt==1)
                
{
                    l[
1].x1=i;
                    l[
1].y1=j;
                    cnt
++;
                }

                
else if(cnt==2)
                
{

                    l[
1].x2=i;
                    l[
1].y2=j;
                }

            }


            
else if(str[j]=='H')
            
{
                m[i][j]
=-1;
                
if(cnt2==1)
                
{
                    hx1
=i;
                    hy1
=j;
                    cnt2
++;
                }

                
else if(cnt2==2)
                
{

                    hx2
=i;
                    hy2
=j;
                }

            }

                
            
else if(str[j]=='.')
                m[i][j]
=0;
        }

    }

}

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1} };


int main()
{

    
int t;
    scanf(
"%d",&t);
    
while(t--)
    
{
        
int i;
        memset(v,
false,sizeof(v));
        scanf(
"%d%d",&n,&mm);
        input(n,mm);
        v[l[
1].x1][l[1].y1][l[1].x2][l[1].y2]=true;
        l[
1].time=0;
        
int front,rear;
        front
=rear=1;
        
while(front<=rear)
        
{
            
            
if(m[l[front].x1][l[front].y1]==-1&&m[l[front].x2][l[front].y2]==-1&&(l[front].x1!=l[front].x2||l[front].y1!=l[front].y2))
                
break;            

            
for(i=0;i<4;i++)
            
{
                
int tx1=l[front].x1;
                
int ty1=l[front].y1;
                
int tx2=l[front].x2;
                
int ty2=l[front].y2;
                
int tt=l[front].time;//存下步数
                
                
if(i==0)
                
{

                    
if(tx1>tx2)
                    
{
                        myswap(tx1,tx2);
                        myswap(ty1,ty2);
                    }

                }

                
else if(i==1)
                
{
                    
if(ty1<ty2)
                    
{
                        myswap(tx1,tx2);
                        myswap(ty1,ty2);
                    }

                }

                
else if(i==2)
                    
if(tx1<tx2)
                    
{myswap(tx1,tx2);    myswap(ty1,ty2);}
                    
                    
                
else if(i==3)
                
{
                    
if(ty1>ty2)
                    
{
                        myswap(tx1,tx2);
                        myswap(ty1,ty2);
                    }

                }

                
if(m[tx1][ty1]==-1&&(tx1!=tx2||ty1!=ty2) )
                    
goto next1;

                
if(m[tx1][ty1]==-1&&tx1==tx2&&ty1==ty2&&m[tx1+dir[i][0]][ty1+dir[i][1]]==-1<2)
                
{
                    tx1
+=dir[i][0];
                    ty1
+=dir[i][1];
                }


    
                
else if(m[tx1+dir[i][0]][ty1+dir[i][1]]==-1)//下一个位置是洞,且洞中无球
                {
                    
                
//    m[tx1+dir[i][0]][ty1+dir[i][1]]=0;
                
//    m[tx1][ty1]=0;
                    tx1+=dir[i][0];
                    ty1
+=dir[i][1];
                }

                
else if(m[tx1+dir[i][0]][ty1+dir[i][1]]==0)
                
{
                
//    m[tx1+dir[i][0]][ty1+dir[i][1]]=1;
                
//    m[tx2][ty2]=0;
                    tx1+=dir[i][0];
                    ty1
+=dir[i][1];
                }

        
next1:            
//第二个球运动
                if(m[tx2][ty2]==-1)
                    
goto next2;

                
else  if(tx2+dir[i][0]==tx2&&ty2+dir[i][1]==ty2&&((tx1!=hx1||ty1!=hy1)&&(tx2!=hx2||ty2!=hy2)) )
                    
goto next2;


                
else if(m[tx2+dir[i][0]][ty2+dir[i][1]]==-1)
                
{
                    
                
//    m[tx2+dir[i][0]][ty2+dir[i][1]]=0;
                
//    m[tx2][ty2]=0;
                    tx2+=dir[i][0];
                    ty2
+=dir[i][1];
                }

                
else if(m[tx2+dir[i][0]][ty2+dir[i][1]]==0&&(tx2+dir[i][0]!=tx1||ty2+dir[i][1]!=ty1))
                
{
                
//    m[tx2+dir[i][0]][ty2+dir[i][1]]=1;
                
//    m[tx2][ty2]=0;
                    tx2+=dir[i][0];
                    ty2
+=dir[i][1];
                }

            
                
next2:
                
if(!v[tx1][ty1][tx2][ty2])
                
{
                    v[tx1][ty1][tx2][ty2]
=true;
                    v[tx2][ty2][tx1][ty1]
=true;
                    tt
++;
                    rear
++;
                    l[rear].x1
=tx1;
                    l[rear].y1
=ty1;
                    l[rear].x2
=tx2;
                    l[rear].y2
=ty2;
                    l[rear].time
=tt;
                }

            }

            
        
    
            front
++;
        }

        
if(front>rear)
            printf(
"Sorry , sir , my poor program fails to get an answer.\n");
        
else 
            printf(
"%d\n",l[front].time);
    }

    
return 0;
}





最后一题,解题报告上貌似是直接建图做的 我感觉并差集反而更简单
#include<iostream>
using namespace std;
#define N 100001
int f[N];
int r[N];

bool mark[N];






int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}
//查找函数,并压缩路径


int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else 
    
{
        f[a]
=b;
        r[b]
+=(r[a]+1);
    }

    
return 1;
    
}
//合并函数,如果属于同一分支则返回0,成功合并返回1

int main()
{
    
int n;
    
int i;
    
while(scanf("%d",&n)!=EOF)
    
{
        
for(i=0;i<n;i++)
        
{
            f[i]
=i;
            r[i]
=0;
        }

        memset(mark,
false,sizeof(bool)*n);
        
int temp;
        
for(i=0;i<n;i++)
        
{

            scanf(
"%d",&temp);
            
if(i!=temp)
            
{
                
if(Union(i,temp))
                
{

                    mark[i]
=true;
                }

                
else
                
{

                    mark[i]
=true;
                }

            }

            
else
                r[i]
+=1;
            
        }

        
int mm=0;
        
int ma=0;
        
for(i=0;i<n;i++)
        
{

            
if(mark[i]==false&&r[i]>mm)
            
{
                mm
=r[i];
                ma
=i;
            }

        }

        
if(mm==0)
        
{
            printf(
"Trouble\n");
            
continue;
        }

        
int cnt=0;
        
for(i=0;i<n;i++)
        
{

            
if(mark[i]==false&&r[i]==mm)
                cnt
++;

        }

        
if(cnt>1)
        
{

            printf(
"Trouble\n");
            
continue;
        }

        
else
            printf(
"%d\n",ma);



    }

    
return 0;
    
    
}



posted on 2010-02-06 22:21 abilitytao 阅读(1131) 评论(2)  编辑 收藏 引用

评论

# re: 杭电月赛 2.6 2010-02-09 13:54 zmm

题目在哪呢?  回复  更多评论   

# re: 杭电月赛 2.6[未登录] 2010-02-09 15:49 abilitytao

@zmm
杭电2.6号的月赛。。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理