2014
03-07

# Alice’s Cube

Alice has received a hypercube toy as her birthday present. This hypercube has 16 vertices, numbered from 1 to 16, as illustrated below. On every vertex, there is a light bulb that can be turned on or off. Initially, eight of the light bulbs are turned on and the other eight are turned off. You are allowed to switch the states of two adjacent light bulbs with different states (“on” to “off”, and “off” to “on”; specifically, swap their states) in one operation.

Given the initial state of the lights, your task is to calculate the minimum number of steps needed to achieve the target state, in which the light bulbs on the sub cube (1,2,3,4)-(5,6,7,8) are turned off, and the rest of them are turned on.

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. There are about 13000 test cases in total.
For each test case there are 16 numbers in a single line, the i-th number is 1 meaning the light of the i-th vertex on the picture is on, and otherwise it’s off.

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. There are about 13000 test cases in total.
For each test case there are 16 numbers in a single line, the i-th number is 1 meaning the light of the i-th vertex on the picture is on, and otherwise it’s off.

3
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1
0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1

Case #1: 0
Case #2: 1
Case #3: more

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100000;

bool flag[N];
bool ok;
int ans;
{
{1,2,4,8},
{0,3,5,9},
{0,3,6,10},
{1,2,7,11},
{0,5,6,12},
{1,4,7,13},
{2,4,7,14},
{3,5,6,15},
{0,9,10,12},
{1,8,11,13},
{2,8,11,14},
{3,9,10,15},
{4,8,13,14},
{5,9,12,15},
{6,10,12,15},
{7,11,13,14},
};
int A(int x)
{
int i;
int ret = 0;
for(i = 15;i >= 8;i --)
{
ret += (bool)(x&(1<<i));
}
return ret;
}
void dfs(int cur,int dp)
{
if(cur == 255)
{
ok = true;
return;
}
if(ok)
return;
if(dp + A(cur) > ans)
return;
int i,j,k;
for(i = 15;i >= 0;i --)
{
if(cur&(1<<i))
{
for(j = 0;j < 4;j ++)
{
int tmp = 15 - adj[15-i][j];
if(((cur>>tmp)&1)^((cur>>i)&1))//!!!!!
{
int tp = cur;
tp ^= (1<<i);
tp ^= (1<<tmp);
if(flag[tp] == false)
{
flag[tp] = true;
dfs(tp,dp + 1);
flag[tp]= false;
}
}
}
}
}
}
int main()
{
int t,i,cas = 0;
scanf("%d",&t);
int a[20];
while(t --)
{
printf("Case #%d: ",++cas);
for(i = 0;i < 16;i ++)
scanf("%d",a + i);
int tmp = 0;
for(i = 0;i < 8;i ++)
tmp += a[i];
if(tmp > 3)
{
printf("more\n");
continue;
}
tmp = 0;
for(i = 15;i >= 0;i --)
{
if(a[i])
tmp |= (1<<(15 - i));
}
ans = -1;
while(1)
{
ans ++;
ok = false;
flag[tmp] = true;
dfs(tmp,0);
flag[tmp] = false;
if(ok)
break;
if(ans >= 3)
{
ans ++;break;
}

}
if(ans > 3)
puts("more");
else
printf("%d\n",ans);
}
return 0;
}

1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。