POJ 1222 Extended Lights Out 题解 《挑战程序设计竞赛》

POJ 1222 Extended Lights Out

灭灯：有6 * 5的灯，一把下去可能关掉或点亮上下左右中5个灯，希望灭掉所有的灯，求灭灯方案。

3.2常用技巧精选（一）

反转

枚举第一行是否需要按开关就行了，第一行固定了的话，第二行也固定了。没睡，A一题醒醒神。

#include <iostream>
#include <numeric>
#include <iterator>
using namespace std;
int light[5][6];
// 邻接的格子的坐标
const int dx[5] = { -1, 0, 0, 0, 1 };
const int dy[5] = { 0, -1, 0, 1, 0 };

int opt[5][6];	// 保存最优解
int flip[5][6];	// 保存中间结果

// 查询（x, y）的颜色
int get(const int& x, const int& y)
{
	int c = light[y][x];
	for (int d = 0; d < 5; ++d)
	{
		int x2 = x + dx[d], y2 = y + dy[d];
		if (0 <= x2 && x2 < 6 && 0 <= y2 && y2 < 5)
		{
			c += flip[y2][x2];
		}
	}

	return c & 1;
}

// 求出第一行确定情况下的最小操作次数
int calc()
{
	// 求出从第二行开始的翻转方法
	for (int i = 1; i < 5; ++i)
	{
		for (int j = 0; j < 6; ++j)
		{
			if (get(j, i - 1) != 0)
			{
				flip[i][j] = 1;
			}
		}
	}
	// 判断最后一行是否全是0
	for (int j = 0; j < 6; ++j)
	{
		if (get(j, 5 - 1) != 0)
		{
			return -1;
		}
	}
	// 统计翻转的次数
	return accumulate(flip[0], flip[0] + 5 * 6, 0);
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	for (int id = 1; id <= n; ++id)
	{
		for (int i = 0; i < 5; ++i)
		{
			for (int j = 0; j < 6; ++j)
			{
				cin >> light[i][j];
			}
		}

		// 按照字典序尝试第一行的所有可能
		for (int i = 0; i < 1 << 6; ++i)
		{
			memset(flip, 0, sizeof(flip));
			for (int j = 0; j < 6; ++j)
			{
				flip[0][6 - j - 1] = i >> j & 1;
			}

			if (calc() >= 0)
			{
				cout << "PUZZLE #" << id << endl;
				for (int i = 0; i < 5; ++i)
				{
					copy(flip[i], flip[i] + 6, ostream_iterator<int>(cout, " "));
					cout << endl;
				}
				break;
			}
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

是不是凌晨特容易刷出0MS啊

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1222 Extended Lights Out 题解 《挑战程序设计竞赛》