The Clocks 时钟 (IOI'94 - Day 2)
考虑将如此安排在一个 3 x 3 行列中的九个时钟:描述
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
目标要找一个最小的移动顺序将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。
移动方法 受影响的时钟 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI
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:
(file clocks.in)
第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。
OUTPUT FORMAT:
(file clocks.out)
单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。
如果有多种方案，输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。
SAMPLE INPUT
9 9 12 6 6 6 6 3 6
SAMPLE OUTPUT
4 5 8 9
算法分析：
方法1：枚举：因为方法的使用顺序不影响最后结果，所以我们只用考虑每一种方法使用了几次，用一个s[i]数组记录，对于每一个s[i]从0-3枚举一次，算出对每一个钟的影响后是否满足条件即可。using namespace std;
/* ID: 138_3531 LANG: C++ TASK: clocks */ #include <algorithm> #include <climits> #include <cstdio> #include <numeric> using namespace std; #define LOOP(x) for (s[x] = 0; s[x] < 4; ++s[x]) //枚举每一种方法用了几次 int main() { int a[9], b[9], cnt, min_cnt = INT_MAX, res[10], s[10]; freopen("clocks.in", "r", stdin); freopen("clocks.out", "w", stdout); for (int i = 0; i < 9; ++i) scanf("%d", &a[i]), a[i] = a[i]/3%4; LOOP(1) LOOP(2) LOOP(3) LOOP(4) LOOP(5) LOOP(6) LOOP(7) LOOP(8) LOOP(9) { b[0] = (a[0]+s[1]+s[2]+s[4])%4; //b[]记录钟表最后状态，a[]记录初试状态，s[]是第i种方法用了几次 b[1] = (a[1]+s[1]+s[2]+s[3]+s[5])%4; b[2] = (a[2]+s[2]+s[3]+s[6])%4; b[3] = (a[3]+s[1]+s[4]+s[5]+s[7])%4; b[4] = (a[4]+s[1]+s[3]+s[5]+s[7]+s[9])%4; b[5] = (a[5]+s[3]+s[5]+s[6]+s[9])%4; b[6] = (a[6]+s[4]+s[7]+s[8])%4; b[7] = (a[7]+s[5]+s[7]+s[8]+s[9])%4; b[8] = (a[8]+s[6]+s[8]+s[9])%4; if (accumulate(b, b+9, 0)) continue; cnt = accumulate(s+1, s+10, 0); if (cnt < min_cnt) { min_cnt = cnt; copy(s+1, s+10, res+1); } } for (int i = 1; i < 10; ++i) while (res[i]--) printf("%d%c", i, --cnt ? ' ' : '\n'); }
深搜DFS： （思想和枚举一样）
/*
ID: 138_3531
LANG: C++
TASK: clocks
*/
#include <iostream>
#include <fstream>
#include <numeric>
using namespace std;
int t[10];
int b[10];
int s[10];
int path[1000];
int pnum;
int minn;
void dfs(int n)
{
if (n==10)
{
b[1] = (t[1]+s[1]+s[2]+s[4])%4; //b[]记录钟表最后状态，a[]记录初试状态，s[]是第i种方法用了几次
b[2] = (t[2]+s[1]+s[2]+s[3]+s[5])%4;
b[3] = (t[3]+s[2]+s[3]+s[6])%4;
b[4] = (t[4]+s[1]+s[4]+s[5]+s[7])%4;
b[5] = (t[5]+s[1]+s[3]+s[5]+s[7]+s[9])%4;
b[6] = (t[6]+s[3]+s[5]+s[6]+s[9])%4;
b[7] = (t[7]+s[4]+s[7]+s[8])%4;
b[8] = (t[8]+s[5]+s[7]+s[8]+s[9])%4;
b[9] = (t[9]+s[6]+s[8]+s[9])%4;
char ok=1;
for (int i=1;i<=9;i++)
if (b[i]!=0)
{
ok=0;
break;
}
if (ok==1)
{
if (accumulate(s+1,s+10,0)<minn)
{
pnum=0;
for (int i=1;i<=9;i++)
{
int m=s[i];
while (m--)
{
path[pnum]=i;
pnum++;
}
}
pnum--;
}
}
return;
}
for (s[n]=0;s[n]<4;s[n]++)
{
dfs(n+1);
}
return;
}
int main()
{
ofstream fout("clocks.out");
ifstream fin("clocks.in");
int count=1;
minn=1000;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
{
fin>>t[count];
t[count]=t[count]/3%4;
count++;
}
dfs(1);
for (int i=0;i<pnum;i++)
fout<<path[i]<<' ';
fout<<path[pnum]<<endl;
return 0;
}