题意：给你一个3*3的翻转模版，深色部分表示翻转，浅色部分不变。然后你可以在r*c的矩形里依照模版进行翻转，要求所有点亮所有块。输出最小的步骤。
思路：有一点比较好想。每个块至多被翻转一次，翻两次的效果是一样的。这样可以搜索，大约2^25，会超时。考虑剪枝。对于每次翻转，只会影响与它临近的几个块，也就是说如果在该块的往上数第2行之前有没亮的块，那么无论之后怎么样，最后一定不会全亮，因为后面的块根本不会影响到前面这些。
这里可以用二进制表示状态。代码写的比较糟乱。
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
][];
bool judge(int x,int y)
{
<=x&&x<n&&<=y&&y<m;
}
int flip(int state,int p)
{
][]= {};
; i<n*m; ++i)
<<i)) st[i/m][i%m]=true;
else st[i/m][i%m]=false;
int x=p/m,y=p%m;
][]&&judge(x-,y-)) st[x-][y-]=!st[x-][y-];
][]&&judge(x-,y)) st[x-][y]=!st[x-][y];
][]&&judge(x-,y+)) st[x-][y+]=!st[x-][y+];
][]&&judge(x,y-)) st[x][y-]=!st[x][y-];
][]&&judge(x,y)) st[x][y]=!st[x][y];
][]&&judge(x,y+)) st[x][y+]=!st[x][y+];
][]&&judge(x+,y-)) st[x+][y-]=!st[x+][y-];
][]&&judge(x+,y)) st[x+][y]=!st[x+][y];
][]&&judge(x+,y+)) st[x+][y+]=!st[x+][y+];
;
; i<n; ++i)
; j<m; ++j)
<<(i*m+j));
return res;
}
][];
int bitcount(int state)
{
;
; i<n*m; ++i)
<<i))
cnt++;
return cnt;
}
bool check(int state,int p)
{
; i<p; ++i)
<<i)))
return false;
return true;
}
void dfs(int cur,int state,int use)
{
if(cur>=n*m)
{
<<m*n)-)
{
||bitcount(use)<bitcount(ans))
ans=use;
}
return ;
}
int x=cur/m,y=cur%m;
&&!check(state,m*(x-))) return;
dfs(cur+,flip(state,cur),use|(<<cur));
dfs(cur+,state,use);
}
int main()
{
;
while(scanf("%d%d",&n,&m)&&!(!n&&!m))
{
ans=-;
; i<; ++i)
{
scanf("%s",g[i]);
; j<; ++j)
ok[i][j]=(g[i][j]=='*');
}
printf("Case #%d\n",++kase);
dfs(,,);
)
puts("Impossible.");
else
{
bool fir=false;
; i<n*m; ++i)
<<i))
);
else
{
fir=true;
printf();
}
printf("\n");
}
}
;
}
/*
5 3
...
***
...
*/