程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj The Clocks（暴搜）

poj The Clocks（暴搜）

編輯：C++入門知識

大致題意：輸入一個3*3的矩陣，其中0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock；現在需要最少的移動使9個時鐘都撥到12點的位置。題中共有9種不同的移動方法，每移動一次，其對應時鐘都會順時針旋轉90度。

思路：這題與模2的開關問題類似。開關只有兩種狀態，即開和關。時鐘有4種狀態，即0,1,2,3。看了網上的解法，都用暴搜做的，因為每種移動方法都只能移動0,1,2,3次，所以可以對每種移動方法進行枚舉。共4^9種可能,不會TLE。所以直接暴搜吧。

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-8

using namespace std;

int main()
{
    int a[10],b[10],c[10];

    for(int i = 1; i <= 9; i++)
        scanf(%d,&a[i]);
    //枚舉每一種移動方法，每一種可實施0,1,2,3次
    for(b[1] = 0; b[1] <= 3; b[1]++)
    for(b[2] = 0; b[2] <= 3; b[2]++)
    for(b[3] = 0; b[3] <= 3; b[3]++)
    for(b[4] = 0; b[4] <= 3; b[4]++)
    for(b[5] = 0; b[5] <= 3; b[5]++)
    for(b[6] = 0; b[6] <= 3; b[6]++)
    for(b[7] = 0; b[7] <= 3; b[7]++)
    for(b[8] = 0; b[8] <= 3; b[8]++)
    for(b[9] = 0; b[9] <= 3; b[9]++)
    {
        c[1] = (a[1] + b[1] + b[2] + b[4])%4;
        c[2] = (a[2] + b[1] + b[2] + b[3] + b[5])%4;
        c[3] = (a[3] + b[2] + b[3] + b[6])%4;
        c[4] = (a[4] + b[1] + b[4] + b[5] + b[7])%4;
        c[5] = (a[5] + b[1] + b[3] + b[5] + b[7] + b[9])%4;
        c[6] = (a[6] + b[3] + b[5] + b[6] + b[9])%4;
        c[7] = (a[7] + b[4] + b[7] + b[8])%4;
        c[8] = (a[8] + b[5] + b[7] + b[8] + b[9])%4;
        c[9] = (a[9] + b[6] + b[8] + b[9])%4;
        if(c[1] + c[2] + c[3] + c[4] + c[5] + c[6] + c[7] + c[8] + c[9] == 0)
        {
            for(int i = 0; i < b[1]; i++) printf(1 );
            for(int i = 0; i < b[2]; i++) printf(2 );
            for(int i = 0; i < b[3]; i++) printf(3 );
            for(int i = 0; i < b[4]; i++) printf(4 );
            for(int i = 0; i < b[5]; i++) printf(5 );
            for(int i = 0; i < b[6]; i++) printf(6 );
            for(int i = 0; i < b[7]; i++) printf(7 );
            for(int i = 0; i < b[8]; i++) printf(8 );
            for(int i = 0; i < b[9]; i++) printf(9 );
            printf(
);
            return 0;
        }
    }
}