UVA 321 The New Villa

UVA_321

这个题目可以把所有灯的开关状态以及当前人所在的屋子看成一个状态，这样的话最多只有n*2^n个状态，由于n很小，还是可以接受的，直接进行隐式图搜索即可。

在用Hash判重时，为了方便我们只把灯的状态用2进制转成哈希码，在判重的时候除了要灯的状态一致人所在的屋子也要一致，满足这个两个条件的状态才可以忽略。

另外在搜索的时候也要注意一些条件，比如人不能熄灭当前所在屋子的灯，在进入下一个房间时一定要保证下一个房间的灯是亮的。

#include<stdio.h>
#include<string.h>
int st[50000][11],now[50000],target[11];
int flag[50000],num[50000],fa[50000],dis[50000];
int G[20][20],L[20][20],r,d,s;
int head[10007],next[50000];
int hash(int *a)
{
    int i,v=0;
    for(i=1;i<=r;i++)
        v=v<<1+a[i];
    return v%10007;
}
int insert(int p)
{
    int i,h;
    h=hash(st[p]);
    for(i=head[h];i!=-1;i=next[i])
        if(memcmp(st[i],st[p],sizeof(st[i]))==0&&now[i]==now[p])
            break;
    if(i==-1)
    {
        next[p]=head[h];
        head[h]=p;
        return 1;
    }
    else
        return 0;
}
void printpath(int a)
{
    if(fa[a]!=-1)
        printpath(fa[a]);
    else
        return;
    if(flag[a]==1)
        printf("- Move to room %d.\n",num[a]);
    else if(flag[a]==2)
        printf("- Switch on light in room %d.\n",num[a]);
    else
        printf("- Switch off light in room %d.\n",num[a]);
}
int main()
{
    int i,j,k,t,p,front,rear;
    t=0;
    while(scanf("%d%d%d",&r,&d,&s)==3)
    {
        if(r==0)
            break;
        memset(G,0,sizeof(G));
        memset(L,0,sizeof(L));
        for(i=0;i<d;i++)
        {
            scanf("%d%d",&j,&k);
            G[j][k]=G[k][j]=1;
        }
        for(i=0;i<s;i++)
        {
            scanf("%d%d",&j,&k);
            L[j][k]=1;    
        }
        front=rear=0;
        memset(st[0],0,sizeof(st[0]));
        st[0][1]=1;
        now[0]=1;
        dis[0]=0;
        fa[0]=-1;
        memset(head,-1,sizeof(head));
        insert(0);
        rear++;
        memset(target,0,sizeof(target));
        target[r]=1;
        while(front<rear)
        {
            if(memcmp(target,st[front],sizeof(target))==0&&now[front]==r)
                break;
            p=now[front];
            for(i=1;i<=r;i++)
                if(G[p][i]&&st[front][i]==1)
                {
                    memcpy(st[rear],st[front],sizeof(st[rear]));
                    now[rear]=i;
                    if(insert(rear))
                    {
                        dis[rear]=dis[front]+1;
                        fa[rear]=front;
                        flag[rear]=1;
                        num[rear]=i;
                        rear++;
                    }
                }
            for(i=1;i<=r;i++)
                if(L[p][i]&&i!=now[front])
                {
                    memcpy(st[rear],st[front],sizeof(st[rear]));
                    now[rear]=now[front];
                    if(st[front][i]==1)
                    {
                        st[rear][i]=0;
                        if(insert(rear))
                        {
                            dis[rear]=dis[front]+1;
                            fa[rear]=front;
                            flag[rear]=3;
                            num[rear]=i;
                            rear++;
                        }
                    }
                    else if(st[front][i]==0)
                    {
                        st[rear][i]=1;
                        if(insert(rear))
                        {
                            dis[rear]=dis[front]+1;
                            fa[rear]=front;
                            flag[rear]=2;
                            num[rear]=i;
                            rear++;
                        }
                    }
                }
            front++;
        }
        printf("Villa #%d\n",++t);
        if(front==rear)
            printf("The problem cannot be solved.\n");
        else
        {
            printf("The problem can be solved in %d steps:\n",dis[front]);
            printpath(front);    
        }
        printf("\n");
    }
    return 0;    
}