题解 P3671 【[USACO17OPEN]Where's Bessie? 贝西在哪呢】

· · 题解

最近一直在刷老题目，很久没有发过题解了（嘻嘻，还是一如既往地菜）

这是一道较为繁琐的搜索题，难并不在搜索过程，而是在判断“两种颜色一种构成一个连通块，另一种形成两个或两个以上的连通块”和“是否被其它PCL覆盖”这两个过程（也就是模拟）。如果没有很好的处理方法，代码很容易写得十分冗长。我这份代码跑了176ms，比楼下两位的题解快一些，写法稍简洁一些，希望能给大家以帮助。

code：

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,-1,0,1}; //两个方向数组，dfs/bfs标配
const int dy[4]={-1,0,1,0};
int n,cnt=0,sum[100],ans=0; //ans存储答案
char a[25][25]; //a数组存储矩阵
bool f[100],v[25][25]; //v数组判断是否搜过，f数组用于记录一个PCL内的某种颜色是否出现过
struct pcl
{
  int x1,y1,x2,y2;
}s[50000]; //s数组存储每个PCL的左上角及右下角的横纵坐标
void dfs(int x,int y,int n1,int n2,int m1,int m2)
{ //深搜划分连通块，注意判断越界的标准不再是整个矩阵的1和n了
  for(int i=0; i<4; i++)
  {
    int x1=x+dx[i],y1=y+dy[i];
    if(x1<n1||x1>n2||y1<m1||y1>m2||v[x1][y1]||a[x1][y1]!=a[x][y]) continue;
    v[x1][y1]=true;
    dfs(x1,y1,n1,n2,m1,m2); //递归深搜
  }
}
bool PCL(int u1,int v1,int u2,int v2) //判断当前矩阵是否是PCL
{
  int col=0; char c1,c2; //c1和c2存储矩阵中的两种不同颜色
  memset(f,0,sizeof(f));
  for(int i=u1; i<=u2; i++) //以下统计当前矩阵中的不同颜色的个数
    for(int j=v1; j<=v2; j++)
      if(!f[a[i][j]]) 
      { 
        f[a[i][j]]=true; 
        col++; 
        if(col==1) c1=a[i][j];
        if(col==2) c2=a[i][j];
      }
  if(col!=2) return false; //如果不同颜色数不为2，返回false
  memset(sum,0,sizeof(sum)); //sum数组存储每个颜色的连通块的个数
  memset(v,0,sizeof(v));
  for(int i=u1; i<=u2; i++)
    for(int j=v1; j<=v2; j++)
      if(!v[i][j]) //如果未搜索过
      {
        v[i][j]=true; //标记
        sum[a[i][j]]++; //sum数组++
        dfs(i,j,u1,u2,v1,v2); //深搜
      }
  if((sum[c1]==1&&sum[c2]>=2)||(sum[c1]>=2&&sum[c2]==1)) return true; //若满足条件2则返回true表示当前矩阵是一个PCL
    else return false;
}
bool judge(int x) //去重过程，判断第x个PCL是否被别的PCL所覆盖
{
  for(int i=1; i<=cnt; i++)
  {
    if(i!=x&&s[i].x1<=s[x].x1&&s[i].y1<=s[x].y1&&s[i].x2>=s[x].x2&&s[i].y2>=s[x].y2)
      return false;
  }
  return true;
}
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++) 
    for(int j=1; j<=n; j++) cin>>a[i][j]; //读入矩阵
  for(int i=1; i<=n; i++) //四重循环暴力枚举每个矩阵的左上角和右下角坐标并做判断
    for(int j=1; j<=n; j++)
      for(int k=i; k<=n; k++)
        for(int l=j; l<=n; l++)
          if(PCL(i,j,k,l))
          { //若当前矩阵是PCL则记录下来
            cnt++;
            s[cnt].x1=i; s[cnt].y1=j; s[cnt].x2=k; s[cnt].y2=l;
          }
  for(int i=1; i<=cnt; i++) //完成去重，累计答案
    if(judge(i)) ans++;
  cout<<ans<<endl; //输出
  return 0;
}

希望对您有帮助！（话说做USACO月赛题的人好少）