题目（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数组后先计算出方案值，排一次序，之后才进行递推操作。
Comments NOTHING