浙江财经大学
信息管理与工程学院

HDU 3220 Alice’s Cube

本文由 Ocrosoft 于 2016-10-15 17:08:16 发表

Alice’s Cube

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2007    Accepted Submission(s): 672

Problem Description

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.

 

Input
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.
 

Output
For every test cases output a number with case number meaning the minimum steps needed to achieve the goal. If the number is larger than 3, you should output “more”.
 

Sample Input
	
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
 

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

Solution
题意:有如图一个超立方体,每个顶点都有一盏灯,如果相邻的两盏灯状态不同,那么可以交换他们的状态。给出一个状态,输出将其变成0000000011111111的状态,如果超过3步,就输出more。
思路:从给出的状态往后BFS,这样会超时,因为数据比较多。所以要考虑从最终状态往前推3步,打好表再去处理答案。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..//
int a[20][5];
int vis[1 << 16];
struct Node
{
	int step, sta;
}t;
void init()
{
	a[1][0] = 2, a[1][1] = 3, a[1][2] = 5, a[1][3] = 9;
	a[2][0] = 1, a[2][1] = 4, a[2][2] = 6, a[2][3] = 10;
	a[3][0] = 1, a[3][1] = 4, a[3][2] = 7, a[3][3] = 11;
	a[4][0] = 2, a[4][1] = 3, a[4][2] = 8, a[4][3] = 12;
	a[5][0] = 1, a[5][1] = 6, a[5][2] = 7, a[5][3] = 13;
	a[6][0] = 2, a[6][1] = 5, a[6][2] = 8, a[6][3] = 14;
	a[7][0] = 3, a[7][1] = 5, a[7][2] = 8, a[7][3] = 15;
	a[8][0] = 4, a[8][1] = 6, a[8][2] = 7, a[8][3] = 16;
	a[9][0] = 1, a[9][1] = 10, a[9][2] = 11, a[9][3] = 13;
	a[10][0] = 2, a[10][1] = 9, a[10][2] = 12, a[10][3] = 14;
	a[11][0] = 3, a[11][1] = 9, a[11][2] = 12, a[11][3] = 15;
	a[12][0] = 4, a[12][1] = 10, a[12][2] = 11, a[12][3] = 16;
	a[13][0] = 5, a[13][1] = 9, a[13][2] = 14, a[13][3] = 15;
	a[14][0] = 6, a[14][1] = 10, a[14][2] = 13, a[14][3] = 16;
	a[15][0] = 7, a[15][1] = 11, a[15][2] = 13, a[15][3] = 16;
	a[16][0] = 8, a[16][1] = 12, a[16][2] = 14, a[16][3] = 15;
}
void bfs()
{
	queue<Node> q;
	t.step = 1, t.sta = 255;
	vis[t.sta] = t.step;
	q.push(t);
	while (!q.empty())
	{
		t = q.front(); q.pop();
		if (t.step >= 4)continue;
		int tmp[20] = { 0 };
		for (int i = 16; i >= 1; i--, t.sta /= 2)
			tmp[i] = t.sta % 2;
		for (int i = 1; i <= 16; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				if (tmp[i] != tmp[a[i][j]])
				{
					Node tt = t; tt.sta = 0; tt.step++;
					swap(tmp[i], tmp[a[i][j]]);
					for (int k = 1; k <=16; k++)tt.sta = tt.sta * 2 + tmp[k];
					swap(tmp[i], tmp[a[i][j]]);
					if (vis[tt.sta])continue;
					vis[tt.sta] = tt.step;
					q.push(tt);
				}
			}
		}
	}
}
int main()
{
	init();
	bfs();
	int n;
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)
		{
			int m = 0;
			for (int j = 0; j < 16;j++)
			{
				int tmp; cin >> tmp;
				m = m * 2 + tmp;
			}
			if (vis[m] && vis[m] <= 4)
				printf("Case #%d: %d\n", i + 1, vis[m] - 1);
			else
				printf("Case #%d: more\n", i+1);
		}
	}
	return 0;
}

 
 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 3220 Alice’s Cube

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址