Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一次AC,还有点难得。。用的是深搜。。

Posted by ckcz123 at 2012-09-08 16:05:29 on Problem 1166
#include <iostream>
using namespace std;

int a[9];

void f(int i)
{
    switch (i)
    {
    case 1:
        a[0]++;a[1]++;a[3]++;a[4]++;break;
    case 2:
        a[0]++;a[1]++;a[2]++;break;
    case 3:
        a[1]++;a[2]++;a[4]++;a[5]++;break;
    case 4:
        a[0]++;a[3]++;a[6]++;break;
    case 5:
        a[1]++;a[3]++;a[4]++;a[5]++;a[7]++;break;
    case 6:
        a[2]++;a[5]++;a[8]++;break;
    case 7:
        a[3]++;a[4]++;a[6]++;a[7]++;break;
    case 8:
        a[6]++;a[7]++;a[8]++;break;
    default:
        a[4]++;a[5]++;a[7]++;a[8]++;break;
    }
}

void h(int i)
{
    switch (i)
    {
    case 1:
        a[0]--;a[1]--;a[3]--;a[4]--;break;
    case 2:
        a[0]--;a[1]--;a[2]--;break;
    case 3:
        a[1]--;a[2]--;a[4]--;a[5]--;break;
    case 4:
        a[0]--;a[3]--;a[6]--;break;
    case 5:
        a[1]--;a[3]--;a[4]--;a[5]--;a[7]--;break;
    case 6:
        a[2]--;a[5]--;a[8]--;break;
    case 7:
        a[3]--;a[4]--;a[6]--;a[7]--;break;
    case 8:
        a[6]--;a[7]--;a[8]--;break;
    default:
        a[4]--;a[5]--;a[7]--;a[8]--;break;
    }
}

bool g(int a[])
{
    for (int i=0;i<=8;i++)
    {
        if (a[i]%4!=0) return false;
    }
    return true;
}

int main()
{
    for (int i=0;i<=8;i++) cin >> a[i];
    int s=99999,l;
    int c[9];
    int b[9];
    for (b[0]=0;b[0]<=3;b[0]++)
    {
        for (int j=1;j<=b[0];j++) f(1);
        for (b[1]=0;b[1]<=3;b[1]++)
        {
            for (int j=1;j<=b[1];j++) f(2);
            for (b[2]=0;b[2]<=3;b[2]++)
            {
                for (int j=1;j<=b[2];j++) f(3);
                for (b[3]=0;b[3]<=3;b[3]++)
                {
                    for (int j=1;j<=b[3];j++) f(4);
                    for (b[4]=0;b[4]<=3;b[4]++)
                    {
                        for (int j=1;j<=b[4];j++) f(5);
                        for (b[5]=0;b[5]<=3;b[5]++)
                        {
                            for (int j=1;j<=b[5];j++) f(6);
                            for (b[6]=0;b[6]<=3;b[6]++)
                            {
                                for (int j=1;j<=b[6];j++) f(7);
                                for (b[7]=0;b[7]<=3;b[7]++)
                                {
                                    for (int j=1;j<=b[7];j++) f(8);
                                    for (b[8]=0;b[8]<=3;b[8]++)
                                    {
                                        for (int j=1;j<=b[8];j++) f(9);
                                        if (g(a))
                                        {
                                            l=0;
                                            for (int i=0;i<=8;i++) l+=b[i];
                                            if (s>l)
                                            {
                                                s=l;
                                                for (int i=0;i<=8;i++) c[i]=b[i];
                                            }
                                        }
                                        for (int j=1;j<=b[8];j++) h(9);
                                    }
                                    for (int j=1;j<=b[7];j++) h(8);
                                }
                                for (int j=1;j<=b[6];j++) h(7);
                            }
                            for (int j=1;j<=b[5];j++) h(6);
                        }
                        for (int j=1;j<=b[4];j++) h(5);
                    }
                    for (int j=1;j<=b[3];j++) h(4);
                }
                for (int j=1;j<=b[2];j++) h(3);
            }
            for (int j=1;j<=b[1];j++) h(2);
        }
        for (int j=1;j<=b[0];j++) h(1);
    }
    for (int i=0;i<=8;i++)
    {
        for (int j=1;j<=c[i];j++)
            cout << i+1 << " ";
    }
    cout << endl;
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator