Light OJ 1092 Lighted Panels (状压)

OJ 1092 Lighted Panels (状压)"/>

Light OJ 1092 Lighted Panels (状压)

解析：可以参考POJ 3279。不同的是这里要把最上面一行和最左一行一起状压。

[code]:

#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;
const int INF = 0x3f3f3f3f;char mp[10][10];
int n,m,state[10][10],flip[10][10];void init(){int i,j;for(i = 0;i < n;i++){for(j = 0;j < m;j++){state[i][j] = (mp[i][j]=='.');flip[i][j] = 0;}}
}void change(int x,int y){int i,j,xx,yy;for(i = -1;i <= 1;i++){for(j = -1;j <= 1;j++){xx = x+i,yy = y+j;if(xx>=n||xx<0||yy>=m||yy<0) continue;flip[xx][yy] ^= 1;}}
}int calc(){int i,j,res = 0;for(i = 1;i < n;i++){for(j = 1;j < m;j++){if(state[i-1][j-1]^flip[i-1][j-1]){change(i,j);res++;}}}for(j = 0;j < m;j++){if(state[n-1][j]^flip[n-1][j]) return INF;}for(i = 0;i < n;i++){if(state[i][m-1]^flip[i][m-1]) return INF;}return res;
}void sol(){int i,j,S,Ed = 1<<(n+m-1),ans = INF,tmp;for(S = 0;S < Ed;S++){memset(flip,0,sizeof(flip));tmp = 0;for(i = 0;i < n+m-1;i++){if(!(S>>i&1)) continue;tmp++;if(i >= m) change(i-m+1,0);else change(0,i);}ans = min(ans,tmp+calc());}if(ans == INF) puts("impossible");else printf("%d\n",ans);
}int main(){int i,j,cas;scanf("%d",&cas);for(int T=1;T<=cas;T++){scanf("%d%d",&n,&m);for(i = 0;i < n;i++){scanf("%s",mp[i]);}init();printf("Case %d: ",T);sol();}return 0;
}