原题地址：https://www.patest.cn/contests/pat-t-practise/1019

老年选手手速准确度堪忧，写个破搜索差点要了老命……

思路很简单，直接搜索，每次从已有的围墙里任选一个沿上下左右四个方向中的一个进行扩展，扩展结束之后一遍BFS检查现在有多少个洞，有没有动物相连。

需要用set对状态进行去重，可以用 long long 压缩保存状态。下面是代码

#include<bits/stdc++.h>
using namespace std;
int zoo[10][10];
int dx[10]={0,-1,0,1};
int dy[10]={-1,0,1,0};
int fin[10][10],qx[100],qy[100];
set<long long> s;
long long ans;
int n,m,k,h;
//1 cell
//0 animals
//2 obstacles 
inline int place2(int x,int y)
{
  if (x<=0 || y<=0 || x>n || y>m) return -1;
  return fin[x][y];
}
inline bool check(long long now)
{
//  if (now<0) return false;
  long long tt=now;
  int tmp=0,x,y,H=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) fin[i][j]=zoo[i][j];
  while(tt)
  {
    x=(tmp/m)+1;y=(tmp%m)+1;
    if (tt&1) fin[x][y]=2;
    tmp++;
    tt>>=1;
  }
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      if (fin[i][j]==2) continue;
      bool hole=true;
      int ani=(fin[i][j]==0);
      int t=1,w=1;
      qx[t]=i;
      qy[t]=j;
      fin[i][j]=2;
      while(t<=w)
      {
        int xx=qx[t],yy=qy[t];
        t++;
        for(int d=0;d<4;d++)
        {
          int res=place2(xx+dx[d],yy+dy[d]);
          if (res==-1) hole=false;
          else if (res==0 || res==1)
          {
            w++;
            fin[xx+dx[d]][yy+dy[d]]=2;
            qx[w]=xx+dx[d];
            qy[w]=yy+dy[d];
          }
          if (res==0) ani++;
          if (ani>=2) return false;
        }
      }
      if (hole) H++;
      if (H>h) return false;
    }
  if (H==h) return true;
  else return false;
}
inline bool place(long long now,int x,int y)
{
  if (x<=0 || y<=0 || x>n || y>m) return false;
  if (!zoo[x][y]) return false;
  return (!((now>>((x-1)*m+y-1))&1));
}
void dfs(long long now,int num)
{
  if (s.count(now)) return;
  s.insert(now);
  if (num==0) 
  {
    if (check(now)) ans++;
    return;
  }
  long long t=now;
  int tmp=0,x,y;
  while(t)
  {
    if (t&1)
    {
      x=(tmp/m)+1;y=(tmp%m)+1;
      for(int d=0;d<4;d++)
    {
      int xx=x+dx[d],yy=y+dy[d];
      if (place(now,xx,yy)) 
      dfs((now|(1LL<<((xx-1)*m+yy-1))),num-1);
    }
    }
    tmp++;
    t>>=1;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>m>>k>>h;
  for(int i=1;i<=n;i++)
  {
    string ss;
    cin>>ss;
    for(int j=0;j<m;j++) 
      zoo[i][j+1]=((ss[j]=='.')?1:0);

  }
  long long now=0;
  for(int i=n;i>=1;i--)
    for(int j=m;j>=1;j--)
    {
      if (!zoo[i][j]) continue;
        now=1LL<<((i-1)*m+(j-1));
        dfs(now,k-1);
    }
  cout<<ans<<endl;
  return 0;
}