poj The Clocks(暴捜)

2490 ワード

http://poj.org/problem?id=1166
0=12 o'clock,1=3 o'clock,2=6 o'clock,3=9 o'clockの3*3の行列を入力します.9つのクロックが12時の位置にダイヤルするように最小限の移動が必要になりました.問題は全部で9種類の異なる移動方法があって、1回移動するたびに、その対応する時計は時計回りに90度回転します.
考え方:この問題は型2のスイッチの問題と似ている.スイッチはオンとオフの2つの状態しかありません.時計には4つの状態、すなわち0,1,2,3がある.ネット上の解法を見て、すべて暴捜で作ったので、それぞれの移動方法は0,1,2,3回しか移動できないので、それぞれの移動方法を列挙することができます.全部で4^9種類可能で、TLEはできません.だから直接捜査しましょう.
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#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; } } }