PersonalCorpus 版 (精华区)

39072 2002-10-06 02:17:46 Accepted
1301 C++ 00:00.00 472K Big Guava


static int p[10]={1,2,4,8,16,32,64,128,256,512};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1301","r",stdin);
    freopen("c:\\0acm\\zju\\o1301","w",stdout);
#endif

    int i,j,k,t=0,r,d,s,nowr,newstate,endstate;
    bool roomdl[10][10],lightdl[10][10], used[10240],ok;
    short path[10240],from[10240],m[10240],res[10240];

    while (1) {
        scanf("%d%d%d\n",&r,&d,&s);
        if ((r==0)&&(d==0)&&(s==0)) break;
        printf("Villa #%d\n",++t);
        memset(roomdl,0,sizeof(roomdl));
        memset(lightdl,0,sizeof(lightdl));
        memset(used,0,sizeof(used));
        memset(from,0,sizeof(from));
        for (i=0;i<d;i++) {
            scanf("%d%d",&j,&k); j--; k--;
            roomdl[j][k]=true;
            roomdl[k][j]=true;
        }
        for (i=0;i<s;i++) {
            scanf("%d%d",&j,&k); j--; k--;
            lightdl[j][k]=true;
        }
        path[0]=1; i=0;j=1; used[1]=true;
        endstate=((r-1)<<10)+p[r-1];
        ok=false; from[0]=-1;
        while (i<j) {
            nowr=path[i]>>10;
            //move
            for (k=0;k<r;k++) if ((roomdl[nowr][k])&&(path[i]&p[k])) {
                newstate=(path[i]&0x3ff)|(k<<10);
                if (!used[newstate]) {
                    used[newstate]=true;
                    path[j]=newstate;
                    from[j]=i;
                    m[j]=k;
                    if (newstate==endstate) {
                        ok=true;
                        break;
                    }
                    j++;
                }
            }
            if (ok) break;
            // turn on
            for (k=0;k<r;k++) if (lightdl[nowr][k]) {
                newstate=path[i]|p[k];
                if (!used[newstate]) {
                    used[newstate]=true;
                    path[j]=newstate;
                    from[j]=i;
                    m[j]=k+20;
                    if (newstate==endstate) {
                        ok=true;
                        break;
                    }
                    j++;
                }
            }
            if (ok) break;

            // turn off
            for (k=0;k<r;k++) if ((lightdl[nowr][k])&&(k!=nowr)) {
                newstate=path[i]&(0x3fff-p[k]);
                if (!used[newstate]) {
                    used[newstate]=true;
                    path[j]=newstate;
                    from[j]=i;
                    m[j]=k+40;
                    if (newstate==endstate) {
                        ok=true;
                        break;
                    }
                    j++;
                }
            }
            if (ok) break;

            i++;
        }
        if (r==1) printf("The problem can be solved in 0 steps:\n");
        else if (ok) {
            k=0;
            while (j!=-1) {
                res[k++]=j;
                j=from[j];
            }
            printf("The problem can be solved in %d steps:\n",k-1);
            for (i=k-2;i>=0;i--)
                if (m[res[i]]>=40) {
                    j=m[res[i]]-40;
                    printf("- Switch off light in room %d.\n",j+1);
                    continue;
                } else if (m[res[i]]>=20) {
                    j=m[res[i]]-20;
                    printf("- Switch on light in room %d.\n",j+1);
                    continue;
                } else printf("- Move to room %d.\n",m[res[i]]+1);
        } else {
            printf("The problem cannot be solved.\n");
        }
        printf("\n");
    }
}