USACO2007OPEN SILVER Fliptile

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Sun Oct 28 15:29:42 CST 2018

In Category: NoCategory

Description：

给一个 $n\times m$ 棋盘，有些棋子为正面，有些为反面，每次操作会改变这个格子和他周围四个格子的情况，问最少操作方案。

$1\leqslant n,m\leqslant 15$

Solution：

发现只要第一行的方案确定了，就可以递推出整个矩阵的方案，于是 $2^{15}$ 枚举第一行并递推其他行，判断是否有解就是判断第 $n+1$ 行是不是全零，这样可以直接累加个数，复杂度 $O(2^nn^2)$

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 16

int a[MAXN][MAXN];

int ans = 0x3f3f3f3f,anss;

int opt[MAXN][MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&a[i][j]);

	for(int s = 0;s < (1 << m);++s)

	{

		for(int i = 1;i <= m;++i)opt[1][i] = (s >> (i - 1)) & 1;

		for(int i = 2;i <= n + 1;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				opt[i][j] = opt[i - 2][j] ^ opt[i - 1][j - 1] ^ opt[i - 1][j] ^ opt[i - 1][j + 1] ^ a[i - 1][j];

			}

		}

		bool legal = true;

		for(int i = 1;i <= m;++i)

		{

			if(opt[n + 1][i] != 0)

			{

				legal = false;

				continue;

			}

		}

		if(!legal)continue;

		int tot = 0;

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				tot += opt[i][j];

			}

		}

		if(tot < ans)

		{

			ans = tot;

			anss = s;

		}

	}

	if(ans != 0x3f3f3f3f)

	{

		for(int i = 1;i <= m;++i)opt[1][i] = (anss >> (i - 1)) & 1;

		for(int i = 2;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				opt[i][j] = opt[i - 2][j] ^ opt[i - 1][j - 1] ^ opt[i - 1][j] ^ opt[i - 1][j + 1] ^ a[i - 1][j];

			}

		}

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= m;++j)

			{

				printf("%d ",opt[i][j]);

			}

			puts("");

		}

	}

	else

	{

		puts("IMPOSSIBLE");

	}

	return 0;

}

In tag: 玄学

wjh15101051