[vijos1326]十全十美

发布于 2017-09-07  141 次阅读



题目(vijos)
这题看上去是个搜索......
其实还真的需要搜索,具体要搜索什么呢?
这道题明显不可能搜索整张图是否可以,那样的话太麻烦了。
我们发现题目输出有个bug特性:方案值从小到大输出。
另外还有个特性:每个点,要么操作一次,要么不操作。
所以,这道题的方案其实就只与第一行有关。
那么我们就知道搜索哪里了:搜索枚举出第一行共有多少种情况,
再从每种情况向下递推。
......啥?递推?
要使该方案尽量可行,那么就必须让尽量上面的行的点全部变色。
所以,递推策略就是:看当前点上面的那一个点是否变了色,若没有,则在当前点操作一次。如果当前点的上面那一个点已经变了色,那么当前点就不操作。
然后就按照题目输出要求一步一步来吧,最后就做完了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
int n,m,cnt,tot;
//cnt用于记录第一行共有多少种情况,tot用于记录总方案数。
struct answer{
	ll val;//存储当前方案的方案值
	int c[105][20];//存储当前方案的答案
}ans[20];
int a[40005][20];//第一行的每一种情况
int b[20];//搜索用的
bool vis[20];//搜索用的
int map[105][20];//原地图
int now[105][20];//记录当前答案
bool cmp(const answer &i,const answer &j)//比较函数
{
	return i.val<j.val;
}
void dfs(int k,int len,int st)//搜索出第一行的所有情况,存储在a数组里面
{
	if (k==len+1)
	{
		++cnt;
		for (int i=1;i<=m;++i)
			a[cnt][i]=b[i];
		return;
	}
	for (int i=st;i<=m;++i)
	{
		if (vis[i]) continue;
		vis[i]=1;
		b[i]=1;
		dfs(k+1,len,i+1);
		b[i]=0;
		vis[i]=0;
	}
}
inline void update(int x,int y)//在当前点操作,更新原图
{
	now[x][y]=1;
	map[x][y]=!map[x][y];
	map[x+1][y]=!map[x+1][y];
	map[x][y-1]=!map[x][y-1];
	map[x][y+1]=!map[x][y+1];
	map[x-1][y]=!map[x-1][y];
}
inline bool check()//检查该答案是否可行
{
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (!map[i][j]) return false;
	return true;
}
inline bool ditui()//递推过程
{
	for (int i=2;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
		{
			if (!map[i-1][j])
			{
				update(i,j);
			}
		}
	}
	if (!check()) return false;
	return true;
}
inline ll cal(int q)//计算当前方案的方案值
{
	ll p=1;
	ll tmp=0;
	for (int i=1;i<=m;++i)
	{
		if (a[q][i]) tmp=tmp+p;
		p*=10;
	}
	return tmp;
}
int main()
{
	scanf(
	for (int i=0;i<=m;++i)
	{
		memset(b,0,sizeof b);
		dfs(1,i,1);
	}
	for (int i=1;i<=cnt;++i)
	{
		memset(map,0,sizeof map);
		memset(now,0,sizeof now);
		for (int j=1;j<=m;++j)
		{
			if (a[i][j]==1)
				update(1,j);
		}
		if (ditui())
		{
			++tot;
			ans[tot].val=cal(i);
			for (int x=1;x<=n;++x)
				for (int y=1;y<=m;++y)
					ans[tot].c[x][y]=now[x][y];
		}
	}
	if (!tot) puts("Impossible");
	else
	{
		sort(ans+1,ans+tot+1,cmp);
		for (int i=1;i<=tot;++i)
		{
			if (i==11) break;
			printf(
			for (int x=1;x<=n;++x)
			{
				for (int y=1;y<=m;++y)
					printf(
				printf("\n");
			}
			printf("\n");
		}
		printf(
	}
	return 0;
}

你问我ans为什么只开20?
这题水呗~
这也是我做完后才发现的问题。
解决方案其实很简单,在搜索完a数组后先计算出方案值,排一次序,之后才进行递推操作。