POJ-1816 撥鐘問題

2019-11-14 08:59:02

字體：大中小

來源：轉載

供稿：網友

題目

來源

中國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;}