POJ-1816 撥鐘問(wèn)題

2019-11-14 08:59:02

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

題目

來(lái)源

中國(guó)MOOC程序設(shè)計(jì)與算法（二）第一周作業(yè)2 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/2/

限制

總時(shí)間限制: 1000ms 內(nèi)存限制: 65536kB

描述

有9個(gè)時(shí)鐘，排成一個(gè)3*3的矩陣。

示意圖

現(xiàn)在需要用最少的移動(dòng)，將9個(gè)時(shí)鐘的指針都撥到12點(diǎn)的位置。共允許有9種不同的移動(dòng)。如下表所示，每個(gè)移動(dòng)會(huì)將若干個(gè)時(shí)鐘的指針沿順時(shí)針?lè)较驌軇?dòng)90度。

移動(dòng) 影響的時(shí)鐘

1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI

輸入

9個(gè)整數(shù)，表示各時(shí)鐘指針的起始位置，相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開。其中，0=12點(diǎn)、1=3點(diǎn)、2=6點(diǎn)、3=9點(diǎn)。

輸出

輸出一個(gè)最短的移動(dòng)序列，使得9個(gè)時(shí)鐘的指針都指向12點(diǎn)。按照移動(dòng)的序號(hào)從小到大輸出結(jié)果。相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開。

樣例輸入

3 3 0 2 2 2 2 1 2

樣例輸出

4 5 8 9

解題報(bào)告

思路分析

重點(diǎn) 本題和特殊密碼鎖的最相似之處就在于，對(duì)鐘進(jìn)行4次撥動(dòng)操作，將與沒(méi)有進(jìn)行操作等同！因此，9種操作最多進(jìn)行4次（5次及以上沒(méi)有意義），窮舉可得

源代碼

#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; //輸入鐘的初始狀態(tài) 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;}