题目大意

一个 n×m 的网格，有的位置是黑的，有的位置是白的。 你要对网格中的任意格子进行任意次（可以不做）操作，每次操作类型是以下两种之一： ∙  翻转这个格子的颜色，并翻转这个格子四相邻格子的颜色。 ∙  仅翻转这个格子四相邻格子的颜色。 求最少多少次操作能够把这个网格的所有格子都变成白色。

1≤n,m≤10

---

题目分析

考虑使用轮廓线状压dp，最naive的 O(nm4m) 的dp相信大家都会。 考虑压缩状态，我们将对一个格子的操作分为以下三种： ∙  不操作，代价为 0 ∙ 翻转它自己（就是把两个给定操作都执行一次），代价为 2 ∙ 翻转它的邻居，这个操作有两种可能（是否翻转自己），代价为 1 这样分类有什么好处呢？可以发现，如果我对一个格子执行了第三种操作，那么不管相邻格子怎么操作，我都可以不额外考虑相邻格子而使得该格子满足要求。 那么现在我们考虑设格子状态了，可以发现，状态也可以设成三种： ∙ 这个格子对相邻格子没有影响，并且目前该格子是黑色 ∙  这个格子对相邻格子没有影响，并且目前该格子是白色 ∙  这个格子对相邻格子有影响，那么显然它就是执行了列举的第三种操作，我们不需要清楚它具体是什么颜色 那么我们就可以用一个长度为 m 的三进制数来存一个轮廓线的状态，对决策位置的上方和左方的状态进行讨论，用三种操作进行转移就可以了。 具体的转移细节就不在这里讲了，自己去思考一下吧。如果你状态表示得好一点，结合一些比较好的实现技巧，可以让你的程序虽然在做3进制的状压，但依然能够使用各种二进制操作简化和加速计算过程。 时间复杂度 O(nm3m) 。注意这题空间限制有点紧，要滚动一下数组。

---

代码实现

#include <algorithm> #include <iostream> #include <cstdio> #include <cctype> using namespace std; int getnxt() { char ch=getchar(); while (!isdigit(ch)) ch=getchar(); return ch-'0'; } const int N=10; const int M=10; const int S=59049; const int INF=N*M*3; int dig[N][M]; int f[2][S]; int POW[M]; int n,m,s; void pre() { POW[0]=1; for (int i=1;i<M;++i) POW[i]=3ll*POW[i-1]; } void update(int &x,int y){x=min(x,y);} int getsta(int sta,int x,int d) { int u=sta/POW[m-1]%3; if (x>=0) (sta-=u*POW[m-1])+=x*POW[m-1]; return (sta/=3)+=d*POW[m-1]; } int dp() { s=POW[m-1]*3; int cur=1,nxt=0; for (int i=1;i<s;++i) f[nxt][i]=INF; f[nxt][0]=0; for (int i=0;i<n;++i) for (int j=0;j<m;++j) { swap(cur,nxt); for (int s_=0;s_<s;++s_) f[nxt][s_]=INF; for (int s_=0,lst,rst;s_<s;++s_) if (f[cur][s_]!=INF) { lst=s_%3,rst=!j?0:s_/POW[m-1]%3; if (!i||lst!=1) update(f[nxt][getsta(s_,j?rst:-1,dig[i][j]^(rst==2)^(lst==2))],f[cur][s_]); if (!i||lst!=1) update(f[nxt][getsta(s_,j?rst:-1,dig[i][j]^(rst==2)^(lst==2)^1)],f[cur][s_]+2); if (!i||lst) update(f[nxt][getsta(s_,j?(rst==2?rst:rst^1):-1,2)],f[cur][s_]+1); } } int ret=n*m*2; for (int s_=0;s_<s;++s_) { bool judge=1; for (int x=s_;x;x/=3) if (x%3==1) { judge=0; break; } if (judge) ret=min(ret,f[nxt][s_]); } return ret; } int main() { freopen("square.in","r",stdin),freopen("square.out","w",stdout); for (pre();scanf("%d%d",&n,&m),n||m;) { for (int i=0;i<n;++i) for (int j=0;j<m;++j) dig[i][j]=getnxt(); printf("%d\n",dp()); } fclose(stdin),fclose(stdout); return 0; }