View Code of Problem 264

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <functional>
#define rank ra
#define next ne
#define pb push_back
#define hash haha
#define lson rt<<1
#define rson rt<<1|1
#define xlson xl,xmid,xt<<1
#define xrson xmid+1,xr,xt<<1|1
#define ylson yl,ymid,xt,yt<<1
#define yrson ymid+1,yr,xt,yt<<1|1
using namespace std;
typedef long long ll;
const int N=1<<11;
int r,d,s,flag,scp;
string ans;         //最终的路径
vector <int> dv[150];   //房间之间的关系
vector <int> lv[150];   //灯的关系
bool vis[150][N+10];    //状态数组
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
struct node
{
    int s;
    int sta;
    int step;
    string dir;
};
char vs(int k)  //别管~看bfs
{
    char cc;
    cc=k+'a';   //这里随便+一个正常的符号记得输出的时候减回来
    return cc;  //为啥要加这个，不知道，就想这么写。
}
void bfs()
{
    memset(vis,0,sizeof(vis));
    queue<node> que;
    node st;
    st.sta=1;   //初始状态只有第一个房间开着灯
    st.s=1;
    st.step=0;
    que.push(st);
    flag=0;
    node k1;
    string tmp;
    while(!que.empty())
    {
        node k=que.front();
        que.pop();
        if(k.s==r&&k.sta==(1<<(r-1)))   //判断是否到终点且只有最后一个房间开着灯
        {
            printf("The problem can be solved in %d steps:\n",k.step);
            flag=1;
            ans=k.dir;
            break;
        }
        for(int i=0;i<(int)dv[k.s].size();i++)   //首先移动到其他开着灯的房间
        {
            int xx=dv[k.s][i];
            if(vis[xx][k.sta]==0&&((1<<(xx-1))&k.sta))
            {
                k1.s=xx;
                k1.sta=k.sta;
                k1.step=k.step+1;
                tmp=k.dir+"M";
                k1.dir=tmp+vs(k1.s);
                que.push(k1);
                vis[k1.s][k1.sta]=1;
            }
        }
        for(int i=0;i<(int)lv[k.s].size();i++)  //其次依次关闭灯 注意不可关闭当前房间的灯
        {
            int sa=scp^(1<<(lv[k.s][i]-1));     //位运算没想到什么好的实现办法所以写的比较复杂
            k1.s=k.s;                           //可自行手推一遍应该就能明白
            k1.sta=k.sta&sa;
            if(vis[k1.s][k1.sta]==0&&lv[k.s][i]!=k.s)
            {
                k1.step=k.step+1;
                tmp=k.dir+"F";
                k1.dir=tmp+vs(lv[k.s][i]);
                que.push(k1);
                vis[k1.s][k1.sta]=1;
            }
        }
        for(int i=0;i<(int)lv[k.s].size();i++)  //依次开灯 这里位运算过程较为简单
        {
            k1.s=k.s;
            k1.sta=k.sta|(1<<(lv[k.s][i]-1));
            if(vis[k1.s][k1.sta]==0)
            {
                k1.step=k.step+1;
                tmp=k.dir+"N";
                k1.dir=tmp+vs(lv[k.s][i]);
                que.push(k1);
                vis[k1.s][k1.sta]=1;
            }
        }
    }
}
void print_ans()
{
    for(int i=0;i<(int)ans.length();i=i+2)  //根据储存的标记打印答案
    {
        if(ans[i]=='M')
            printf("- Move to room %d.\n",ans[i+1]-'a');
        if(ans[i]=='N')
            printf("- Switch on light in room %d.\n",ans[i+1]-'a');
        if(ans[i]=='F')
            printf("- Switch off light in room %d.\n",ans[i+1]-'a');
    }
}
void init()     //初始化vector
{
    scp=(1<<10)-1;
    for(int i=0;i<=10;i++)
        dv[i].clear();
    for(int i=0;i<=10;i++)
        lv[i].clear();
}
int main()
{
    int kase=0;
    while(scanf("%d%d%d",&r,&d,&s)!=EOF)
    {
        init();
        if(r==0&&d==0&&s==0)
            break;
        int p,q;
        for(int i=1;i<=d;i++)   //建立房间的关系
        {
            scanf("%d%d",&p,&q);
            dv[p].pb(q);
            dv[q].pb(p);
        }
        for(int i=1;i<=s;i++)   //建立灯之间的关系
        {
            scanf("%d%d",&p,&q);
            lv[p].pb(q);
        }
        for(int i=1;i<=s;i++)       //排序
            sort(lv[i].begin(),lv[i].end());
        for(int i=1;i<=d;i++)
            sort(dv[i].begin(),dv[i].end());
        printf("Villa #%d\n",++kase);
        bfs();
        if(flag)
            print_ans();
        else
            printf("The problem cannot be solved.\n");
        printf("\n");
    }
    return 0;
}