UC知道时钟问题（vijosP1016）pascal
来源：百度知道 编辑：UC知道 时间：2024/07/06 13:32:23
在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下： 操作 指定的操作挂钟4 5 8 9
1 ABDE
2 ABC
3BCEF
4ADG
5BDEFH
6CFI
7DEGH
8GHI
9EFHI
输入格式 Input Format
你的程序按照标准的3*3格式读入，一共9个0-3的数。0代表12点，1代表3点，2代表6点，3代表9点。
输出格式 Output Format
你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向12点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。
const act:array[1..9]of string[5]=('ABDE','ABC','BCEF','ADG','BDEFH','CFI','DEGH','GHI','EFHI');
type arr=array[1..9]of integer;
var x:array[1..9]of integer;
time:array[1..9]of integer;
w:array[0..36]of integer;
h,i:integer;
procedure print;
v
方法1：枚举
因为每种变换方法可以使用0~3次，并且每种变换方法在前与在后是等效的。所以，利用递归，按题中顺序枚举所有可能的解，并且每次记录下途径，那么第一种解就是我们要求的答案，输出即可。并且此方法简单易懂，复杂度很低。在usaco上测试最大的才用了0.097秒。 主要程序步骤： const
a:array[1..9,0..9] of byte=((4,1,2,4,5,0,0,0,0,0),
(3,1,2,3,0,0,0,0,0,0),
(4,2,3,5,6,0,0,0,0,0),
(3,1,4,7,0,0,0,0,0,0),
(5,2,4,5,6,8,0,0,0,0),
(3,3,6,9,0,0,0,0,0,0),
(4,4,5,7,8,0,0,0,0,0),
(3,7,8,9,0,0,0,0,0,0),
(4,5,6,8,9,0,0,0,0,0));
记录每种方法改变钟表的情况，a[i,0]表示需要改变的钟表的个数，其后a[i,0]个表示要改变的具体钟表的序号；
... ... procedure try(n:integer;g,b:pp); var i,j,k:integer; begin
if n=10 then 检验是否为可行解；
for k:=0 to 3 do
begin
b[n]:=k;
for i:=1 to a[n,0] do inc(g[a[n,i]],k);//改变钟表；
try(n+1,g,b);