| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一次AC,还有点难得。。用的是深搜。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator