The New Villa

题目：The New Villa

题目链接：http://poj.org/problem?id=1137

题目大意：

　　一个人买了一个别墅，里面有很多房间，特别的是这个别墅的房间里灯的开关是乱套的，也就是说房间1可能没有房间1的灯的开关，而有房间2和房间3的开关，现在从房间1出发，刚开始只有房间1是亮的，只能走到亮着的房间（还必须有门相通），现在问你走到房间n，并且只剩下房间n是亮着的步骤，如果有多个方法，输出步骤最少的。

题目思路：

　　啥也不说，n最大为10，暴力搜，注意剪枝就可以了。。。附上我的代码和代码解析，不过我的代码并不怎么给力，最后时间还是需要250。。。

  1 #include<stdio.h>
  2 #include<string.h>
  3 bool door[11][11];  //门
  4 bool sw[11][11];    //如果i能控制j的灯，那么sw[i][j]=1
  5 int light;          //当前灯的状态，从0到1024
  6 int n;              //房间的总数量
  7 int count[11][11];  //某一扇门被经过的次数，可以用来控制递归次数，减少时间
  8 int num[11];        //记录房间开关的所有状态数量，达不到1024
  9 int nu[11][1024];   //记录每个房间开关的所有状态
 10 bool OK()           //判断是否只有卧室灯开着，结束判断为当前位置为卧室且OK()
 11 {
 12   if(light^(1<<(n-1))) return false;
 13   return true;
 14 }
 15 void Init()                 //初始化，处理每个房间开关可能的状态
 16 {
 17   for(int i=1;i<=n;i++)
 18   {
 19     for(int j=0;j<1024;j++)
 20     {
 21       if((1<<(i-1))&j) continue;  //不允许关掉自己房间的灯
 22       int o;
 23       for(o=1;o<11;o++)
 24       {
 25         if(sw[i][o]==1) continue;
 26         if((1<<(o-1))&j) break;   //如果没有该房间的控制权，不允许对其进行操作
 27       }
 28       if(o<11) continue;
 29       nu[i][num[i]++]=j;
 30     }
 31   }
 32 }
 33 void dis(int tmp)     //测试用。。。。
 34 {
 35   int co=0;
 36   while(tmp)
 37   {
 38     printf("%d ",tmp&1);
 39     tmp>>=1;
 40     co++;
 41   }
 42   co=11-co;
 43   while(co--)
 44   {
 45     printf("0 ");
 46   }
 47   printf("
");
 48 }
 49 
 50 int s[10000][2];         //保存当前的步骤情况
 51 int mint[10000][2],mino; //保存所有能成功的步骤中步骤最小的
 52 bool v[11][1024];        //保存是否遇到过这种情况，与下面的结合使用
 53 int vum[11][1024];       //vum[i][j]表示当前处在房间i，灯的状态为j，最小的步骤，剪枝用
 54 bool match;              //是否能完成任务
 55 void DFS(int i,int step)
 56 {
 57   if(v[i][light]&&step>=vum[i][light]) return ;
 58   //因为下面有个剪枝，通过0状态过去的和这个一样。不在这里刷新值是为了在下面的可以把step>=的都排除掉，更快。
 59   for(int j=0;j<num[i];j++)
 60   {
 61     int k=nu[i][j];        //可行的开关执行方案
 62     int tmp=light;         //保存原来的灯状态
 63     light^=k;              //操作开关
 64     int pre_step=step;     //保存原来的步骤
 65     for(int o=1;o<=n;o++)  //记录步骤
 66     {
 67       if((1<<(o-1))&k)
 68       {
 69         s[step++][0]=o;
 70       }
 71     }
 72     if(v[i][light]&&step>=vum[i][light])     //剪枝
 73     {
 74       light=tmp;
 75       step=pre_step;
 76       continue;
 77     }
 78     v[i][light]=1;
 79     vum[i][light]=step;
 80     if(i==n&&OK())          //如果完成操作
 81     {
 82       if(step<mino)
 83       {
 84         for(int o=0;o<step;o++)
 85         {
 86           mint[o][0]=s[o][0];
 87           mint[o][1]=s[o][1];
 88         }
 89         mino=step;
 90       }
 91       match=1;
 92       light=tmp;
 93       return ;
 94     }
 95     for(int j=1;j<=n;j++)
 96     {
 97       if(door[i][j]==1&&(light&(1<<(j-1))))  //如果有门相通
 98       {
 99         count[i][j]++;
100         if(count[i][j]>n-1)
101         {
102           count[i][j]--;
103           continue;
104         }
105         s[step][1]=j;
106         DFS(j,step+1);      //进入下一个房间
107         s[step][1]=-1;      //只在这里进行恢复，因为这里的恢复比恢复s[step][0]的快很多
108         count[i][j]--;
109       }
110     }
111     light=tmp;
112     step=pre_step;
113   }
114 }
115 void solve()          //展示步骤
116 {
117   int light=1;
118   printf("The problem can be solved in %d steps:
",mino);
119   for(int i=0;i<mino;i++)
120   {
121     if(mint[i][1]==-1)
122     {
123       if(light&(1<<(mint[i][0]-1)))
124       {
125         printf("- Switch off light in room %d.
",mint[i][0]);
126       }
127       else
128       {
129         printf("- Switch on light in room %d.
",mint[i][0]);
130       }
131       light^=(1<<(mint[i][0]-1));
132     }
133     else
134     {
135       printf("- Move to room %d.
",mint[i][1]);
136     }
137   }
138 }
139 int main()
140 {
141   int m,k,a,b,cas=1;
142   while(scanf("%d%d%d",&n,&m,&k)!=EOF)
143   {
144     if(n==0&&m==0&&k==0) break;
145     memset(door,0,sizeof(door));
146     for(int i=0;i<m;i++)
147     {
148       scanf("%d%d",&a,&b);
149       door[a][b]=1;
150       door[b][a]=1;
151     }
152     memset(sw,0,sizeof(sw));
153     memset(num,0,sizeof(num));
154     for(int i=0;i<k;i++)
155     {
156       scanf("%d%d",&a,&b);
157       sw[a][b]=1;
158     }
159     Init();
160     light=1;
161     memset(s,-1,sizeof(s));
162     mino=100000;
163     match=0;
164     memset(v,0,sizeof(v));
165     DFS(1,0);
166     printf("Villa #%d
",cas++);
167     if(match==1)
168     {
169       solve();
170       printf("
");
171     }
172     else printf("The problem cannot be solved.

");
173   }
174   return 0;
175 }