直接状态压缩枚举所有状态判断是否可行，从所有可行方案中找最小的。

题目最大的坑点在于，题目说的是15个点，但亲测最多有16个点，我屮艸芔茻。。。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;int v[1<<16];
char mp[222][222];
int mark[222][222];
int x[20];
int y[20];
int xx[4][3]={0,-1,0,0,1,0,0,0,1,0,-1,0};
int yy[4][3]={0,0,1,0,0,1,0,-1,0,0,0,-1};
int n,m,cnt,s1,s2;void init()
{int m=1<<16-1;      //改成15立马WA，我屮艸芔茻memset(v,0,sizeof(v));for (int i=1;i<=m;i++){int t=i;while (t>0){if (t&1)v[i]++;t>>=1;}}return ;
}void build(int i,int k)
{for (int t=0;t<3;t++)   //重构现场{int nx=x[i]+xx[k][t];int ny=y[i]+yy[k][t];if (nx>n||nx<1||ny>m||ny<1)continue ;if (mp[nx][ny]=='#'){mark[nx][ny]++;if (mark[nx][ny]==1)s2++;}else{mark[nx][ny]++;if (mark[nx][ny]==1)s1++;}}
}void restore(int i,int k)
{for (int t=0;t<3;t++)   //还原现场{int nx=x[i]+xx[k][t];int ny=y[i]+yy[k][t];if (nx>n||nx<1||ny>m||ny<1)continue ;if (mp[nx][ny]=='#'){mark[nx][ny]--;if (mark[nx][ny]==0)s2--;}else{mark[nx][ny]--;if (mark[nx][ny]==0)s1--;}}
}bool getnext(int st)
{memset(mark,0,sizeof(mark));s1=0;s2=0;for (int i=0;i<cnt;i++)     //构造初始的状态形成的覆盖情况if (st&(1<<i))build (i,0);if (s1==cnt&&s2==0)     //如果初始的覆盖已经满足题意，则返回truereturn true;for (int i=0;i<cnt;i++){if (st&(1<<i)){restore(i,0);   //将这个点按照初始形式放的情况删掉for (int k=1;k<=3;k++){build(i,k);     //重构这个节点的新覆盖情况if (s1==cnt&&s2==0)return true;restore(i,k);   //删除这个节点的新覆盖情况}build(i,0);     //重构这个节点的初始构造情况}}return false;
}int main()
{init();while (scanf("%d%d",&n,&m)&&n+m){for (int i=1;i<=n;i++)scanf("%s",mp[i]+1);cnt=0;for (int i=1;i<=n;i++){for (int t=1;t<=m;t++){if (mp[i][t]=='.'){x[cnt]=i;y[cnt]=t;cnt++;}}}int mm=(1<<cnt)-1;int ans=999;for (int i=0;i<=mm;i++){if (v[i]>=ans)continue ;if (getnext(i))ans=v[i];}if (ans==999)ans=-1;printf("%d\n",ans);}
}