1250. 【USACO题库】1.4.2 The Clocks (Standard IO)

1250. 【USACO题库】1.4.2 The Clocks (Standard IO)

时间限制:  1000 ms  空间限制:  262144 KB  具体限制  

题目描述

考虑将如此安排在一个 3 x3 行列中的九个时钟:

|-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C |-------| |-------| |-------| | | | | | | | O | | O | | O | | | | | | | | | | |-------| |-------| |-------| D E F |-------| |-------| |-------| | | | | | | | O | | O---| | O | | | | | | | | | |-------| |-------| |-------| G H I

目标要找一个最小的移动顺序次将所有的指针指向12点。 下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。 选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。

移动方法受影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHI

Example

9 9 12 9 12 12 9 12 12 12 12 12 12 12 12  6 6 6 5 -> 9 9 9 8-> 9 9 9 4 -> 12 9 9 9-> 12 12 12  6 3 6 6 6 6 9 9 9 12 9 9 12 12 12

[但这可能不是正确的方法，请看下面]

PROGRAM NAME: clocks

INPUT FORMAT

第1-3行:三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。 数字的含意和上面第一个例子一样。

SAMPLE INPUT (file clocks.in)

9 9 12 6 6 6 6 3 6

OUTPUT FORMAT

单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。 如果有多种方案，输出那种使的连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

输入

输出

样例输入

样例输出

数据范围限制

统计

通过:  134 提交:  361 平均分:  51.49 提交

标签 添加

题解 添加

服务器时间: Sun Aug 06 2017 04:04:41 GMT-0700 (太平洋夏令时) Fortuna OJ 项目 作者:  moreD ,  RD ; 协力:  twilight 由 Codeigniter / Bootstrap 驱动

Glyphicons 提供图标

哎！又一道淼题！

本来以为很难，事实上......

被洗脑后识破此题本质....

水的不要不要的模拟！

每一个操作不能做4次或以上，否则有重复

枚举每个操作用几次，z递归保证字典序

时间复杂度4^9=262144,1秒内

可过！

标程（请勿抄袭）：

var i,j,k,m,n,o,p,l,s,t:longint; a,g:array[1..3,1..3] of longint; b:array[0..1000] of longint; function jia(t:longint):longint; begin jia:=(t+3) mod 12; if jia=0 then jia:=12; end; procedure turn(t:longint); begin if t=1 then begin g[1,1]:=jia(g[1,1]);g[1,2]:=jia(g[1,2]);g[2,1]:=jia(g[2,1]);g[2,2]:=jia(g[2,2]); end; if t=2 then begin g[1,1]:=jia(g[1,1]);g[1,2]:=jia(g[1,2]);g[1,3]:=jia(g[1,3]); end; if t=3 then begin g[1,2]:=jia(g[1,2]);g[1,3]:=jia(g[1,3]);g[2,2]:=jia(g[2,2]);g[2,3]:=jia(g[2,3]); end; if t=4 then begin g[1,1]:=jia(g[1,1]);g[2,1]:=jia(g[2,1]);g[3,1]:=jia(g[3,1]); end; if t=5 then begin g[1,2]:=jia(g[1,2]);g[2,1]:=jia(g[2,1]);g[2,2]:=jia(g[2,2]);g[2,3]:=jia(g[2,3]);g[3,2]:=jia(g[3,2]); end; if t=6 then begin g[1,3]:=jia(g[1,3]);g[2,3]:=jia(g[2,3]);g[3,3]:=jia(g[3,3]); end; if t=7 then begin g[2,1]:=jia(g[2,1]);g[2,2]:=jia(g[2,2]);g[3,1]:=jia(g[3,1]);g[3,2]:=jia(g[3,2]); end; if t=8 then begin g[3,1]:=jia(g[3,1]);g[3,2]:=jia(g[3,2]);g[3,3]:=jia(g[3,3]); end; if t=9 then begin g[2,2]:=jia(g[2,2]);g[2,3]:=jia(g[2,3]);g[3,2]:=jia(g[3,2]);g[3,3]:=jia(g[3,3]); end; end; procedure dg(t:longint); var i,j:longint; begin if t>9 then begin for i:=1 to b[0] do begin turn(b[i]); end; o:=0; for i:=1 to 3 do for j:=1 to 3 do if g[i,j]<>12 then o:=1; if o=0 then begin for i:=1 to b[0] do write(b[i],' '); halt; end; g:=a; end else begin for i:=0 to 3 do begin for j:=1 to i do begin inc(b[0]); b[b[0]]:=t; end; dg(t+1); dec(b[0],i); end; end; end; begin for i:=1 to 3 do begin for j:=1 to 3 do read(a[i,j]); readln; end; g:=a; b[0]:=0; dg(0); end.