B:拨钟问题
查看
提交 统计 提问总时间限制:
1000ms 内存限制: 65536kB描述
有9个时钟，排成一个3*3的矩阵。现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。
移动 影响的时钟
1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI (图 2) 输入 从标准输入设备读入9个整数，表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。 输出 输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果。 样例输入3 3 0
2 2 2 2 1 2样例输出
4 5 8 9
==============================================
eg.
#include <iostream>
#include <cstdio> using namespace std; int state[5][5] = {0}; int s[5][5] = {0}; int swit[5][5] = {0}; int cop[5][5] = {0}; int sum = 0; int mi = 100;void changeswit(int a, int b, int t)
{ int no = (a - 1) * 3 + b; if(b == 2 && a != 2) { state[a][b - 1] = (state[a][b - 1] + t) % 4; state[a][b] = (state[a][b] + t) % 4; state[a][b + 1] = (state[a][b + 1] + t) % 4; } else if(a == 2 && b != 2) { state[a - 1][b] = (state[a - 1][b] + t) % 4; state[a][b] = (state[a][b] + t) % 4; state[a + 1][b] = (state[a + 1][b] + t) % 4; } else if(a == 2 && b == 2) { state[a][b] = (state[a][b] + t) % 4; state[a - 1][b] = (state[a - 1][b] + t) % 4; state[a + 1][b] = (state[a + 1][b] + t) % 4; state[a][b - 1] = (state[a][b - 1] + t) % 4; state[a][b + 1] = (state[a][b + 1] + t) % 4; } else { int dx[3] = {-1, 0, 1}; int dy[3] = {-1, 0, 1}; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) state[a+dx[i]][b+dy[j]] = (state[a+dx[i]][b+dy[j]] + t) % 4; } return;}
int main() { for(int i = 1; i <= 3; i++) for(int j = 1; j <= 3; j++) scanf("%d",&s[i][j]); for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { for(int k = 0; k < 4; k++) { for(int l = 1; l < 4; l++) for(int m = 1; m < 4; m++) { state[l][m] = s[l][m]; swit[l][m] = 0; } sum = 0;
swit[1][1] = i;
swit[1][2] = j; swit[1][3] = k; changeswit(1,1,i); changeswit(1,2,j); changeswit(1,3,k);if(state[1][1] != 0)
{ swit[2][1] = 4 - state[1][1]; changeswit(2,1,4 - state[1][1]); } if(state[1][3] != 0) { swit[2][3] = 4 - state[1][3]; changeswit(2,3,4 - state[1][3]); } if(state[1][2] != 0) { swit[2][2] = 4 - state[1][2]; changeswit(2,2,4 - state[1][2]); } if(state[2][1] != 0) { swit[3][1] = 4 - state[2][1]; changeswit(3,1,4 - state[2][1]); } if(state[2][3] != 0) { swit[3][3] = 4 - state[2][3]; changeswit(3,3,4 - state[2][3]); } if(state[2][2] != 0) continue; if(state[3][1] == state[3][2] && state[3][1] == state[3][3]) { swit[3][2] = (4 - state[3][1]) % 4; for(int l = 1; l < 4; l++) for(int m = 1; m < 4; m++) sum += swit[l][m]; if(sum < mi) { mi = sum; for(int l = 1; l < 4; l++) for(int m = 1; m < 4; m++) cop[l][m] = swit[l][m]; } } else continue; } } } bool f = 0; for(int i = 1; i < 4; i++) for(int j = 1; j < 4; j++) { while(cop[i][j]--) { if(f) printf(" "); printf("%d", 3*(i - 1) + j); f = 1; } } printf("\n"); return 0; }