POJ-1816 拨钟问题

2019-11-14 08:43:34

字体：大中小

来源：转载

供稿：网友

题目

来源

中国MOOC程序设计与算法（二）第一周作业2 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/2/

限制

总时间限制: 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

输入

9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。

输出

输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。

样例输入

3 3 0 2 2 2 2 1 2

样例输出

4 5 8 9

解题报告

思路分析

重点本题和特殊密码锁的最相似之处就在于，对钟进行4次拨动操作，将与没有进行操作等同！因此，9种操作最多进行4次（5次及以上没有意义），穷举可得

源代码

#include <stdio.h>int clock[9] = {0};int n1 = 0;int n2 = 0;int n3 = 0;int n4 = 0;int n5 = 0;int n6 = 0;int n7 = 0;int n8 = 0;int n9 = 0;int main(){ int i = 0; //输入钟的初始状态 for( i = 0; i < 9; i++ ) { scanf("%d", &clock[i]); } for( n1 = 0; n1 < 4; n1++ ) { for( n2 = 0; n2 < 4; n2++ ) { for( n3 = 0; n3 < 4; n3++ ) { for( n4 = 0; n4 < 4; n4++ ) { for( n5 = 0; n5 < 4; n5++ ) { for( n6 = 0; n6 < 4; n6++ ) { for( n7 = 0; n7 < 4; n7++ ) { for( n8 = 0; n8 < 4; n8++ ) { for( n9 = 0; n9 < 4; n9++ ) { if( isOK( clock ) ) { for( i=0;i<n1;i++ ) printf("1 "); for( i=0;i<n2;i++ ) printf("2 "); for( i=0;i<n3;i++ ) printf("3 "); for( i=0;i<n4;i++ ) printf("4 "); for( i=0;i<n5;i++ ) printf("5 "); for( i=0;i<n6;i++ ) printf("6 "); for( i=0;i<n7;i++ ) printf("7 "); for( i=0;i<n8;i++ ) printf("8 "); for( i=0;i<n9;i++ ) printf("9 "); } c9(); } c8(); } c7(); } c6(); } c5(); } c4(); } c3(); } c2(); } c1(); } return 0;}int isOK( int c[] ){ int r = 1; int i = 0; for( i = 0; i < 9; i++ ) { if( c[i] != 0 ) r = 0; } return r;}void c1(){ clock[0] = (clock[0]+1)%4; clock[1] = (clock[1]+1)%4; clock[3] = (clock[3]+1)%4; clock[4] = (clock[4]+1)%4;}void c2(){ clock[0] = (clock[0]+1)%4; clock[1] = (clock[1]+1)%4; clock[2] = (clock[2]+1)%4;}void c3(){ clock[1] = (clock[1]+1)%4; clock[2] = (clock[2]+1)%4; clock[4] = (clock[4]+1)%4; clock[5] = (clock[5]+1)%4;}void c4(){ clock[0] = (clock[0]+1)%4; clock[6] = (clock[6]+1)%4; clock[3] = (clock[3]+1)%4;}void c5(){ clock[1] = (clock[1]+1)%4; clock[3] = (clock[3]+1)%4; clock[4] = (clock[4]+1)%4; clock[5] = (clock[5]+1)%4; clock[7] = (clock[7]+1)%4;}void c6(){ clock[2] = (clock[2]+1)%4; clock[5] = (clock[5]+1)%4; clock[8] = (clock[8]+1)%4;}void c7(){ clock[3] = (clock[3]+1)%4; clock[4] = (clock[4]+1)%4; clock[6] = (clock[6]+1)%4; clock[7] = (clock[7]+1)%4;}void c8(){ clock[6] = (clock[6]+1)%4; clock[7] = (clock[7]+1)%4; clock[8] = (clock[8]+1)%4;}void c9(){ clock[4] = (clock[4]+1)%4; clock[5] = (clock[5]+1)%4; clock[7] = (clock[7]+1)%4; clock[8] = (clock[8]+1)%4;}