UVa 321：The New Villa

UVa 321：The New Villa2014-10-09 csdn博客 shuangde800题目链接：

UVA ： http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=257

POJ 1137： http://poj.org/problem？id=1137

ZOJ 1301： http://acm.zju.edu.cn/onlinejudge/showProblem.do？problemCode=1301

类型：隐式图搜索

原题：

Mr. Black recently bought a villa in the countryside. Only one thing bothers him: although there are light switches in most rooms, the lights they control are often in other rooms than the switches themselves. While his estate agent saw this as a feature, Mr. Black has come to believe that the electricians were a bit absent-minded （to put it mildly） when they connected the switches to the outlets.

One night, Mr. Black came home late. While standing in the hallway, he noted that the lights in all other rooms were switched off. Unfortunately, Mr. Black was afraid of the dark, so he never dared to enter a room that had its lights out and would never switch off the lights of the room he was in.

After some thought, Mr. Black was able to use the incorrectly wired light switches to his advantage. He managed to get to his bedroom and to switch off all lights except for the one in the bedroom.

You are to write a program that, given a description of a villa, determines how to get from the hallway to the bedroom if only the hallway light is initially switched on. You may never enter a dark room, and after the last move, all lights except for the one in the bedroom must be switched off. If there are several paths to the bedroom, you have to find the one which uses the smallest number of steps, where ``move from one room to another"", ``switch on a light"" and ``switch off a light"" each count as one step.

Sample Input

3 3 41 21 33 21 21 32 13 22 1 22 11 11 20 0 0

Sample Output

Villa #1The problem can be solved in 6 steps:- Switch on light in room 2.- Switch on light in room 3.- Move to room 2.- Switch off light in room 1.- Move to room 3.- Switch off light in room 2.Villa #2The problem cannot be solved.

题目大意：

一个2B青年赚钱了于是乐呵呵地跑去买了一栋别墅，结果却发现这栋别墅的电灯电路都接错了，每个房间里的电灯开关控制的不是这个房间的电灯，而是另一个房间的电灯～～ 2B青年很生气，后果很严重，于是严重谴责了装修工人。

一天晚上2B青年回到家里，站在大厅，发现除了大厅其它房间的电灯全部都是灭的。2B青年很怕黑，不敢走进没开灯的房间。所以问题来了，他该怎样从大厅走到自己的卧室？

2B青年还是很聪明的，他发现正好可以利用电灯开关接错而把另一个房间的电灯打开，然后就可以走进开了灯的那个房间（2B青年不会穿墙术，所以这两个房间当然必须是相邻的并且有门的）。

2B青年也是个很节约用电的好青年，所以当他走到卧室时，要求其它房间都必须把灭掉。

现在是你大显身手的时候，编写一个程序帮2B青年找出一个步骤最少的方案并且输出。开灯，关灯，走进另一个房间都算是一个步骤。如果找不出方案的话，2B青年今晚就得睡大厅沙发了。