[USACO 2017 Ope S]Where's Bessie?

Always known for being quite tech-savy, Farmer John is testing out his new automated drone-mounted cow locator camera, which supposedly can take a picture of his field and automatically figure out the location of cows. Unfortunately, the camera does not include a very good algorithm for finding cows, so FJ needs your help developing a better one.

The overhead image of his farm taken by the camera is described by an N×N grid of characters, each in the range A…Z, representing one of 26 possible colors. Farmer John figures the best way to define a potential cow location (PCL) is as follows: A PCL is a rectangular sub-grid (possibly the entire image) with sides parallel to the image sides, not contained within any other PCL (so no smaller subset of a PCL is also a PCL). Furthermore, a PCL must satisfy the following property: focusing on just the contents of the rectangle and ignoring the rest of the image, exactly two colors must be present, one forming a contiguous region and one forming two or more contiguous regions.

For example, a rectangle with contents

AAAAA ABABA AAABB

would constitute a PCL, since the A's form a single contiguous region and the B's form more than one contiguous region. The interpretation is a cow of color A with spots of color B.

A region is "contiguous" if you can traverse the entire region by moving repeatedly from one cell in the region to another cell in the region taking steps up, down, left, or right.

Given the image returned by FJ's camera, please count the number of PCLs.

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int a[25][25]; int n,ans,num; int flag[25][25]; int color[26],c[10000]; struct answer { int i1,i2,j1,j2; }pcl_[50000]; void find(int x,int i,int j,int i1,int i2,int j1,int j2) { flag[i][j]=1; if(i<i2&&flag[i+1][j]==0&&a[i+1][j]==x) find(x,i+1,j,i1,i2,j1,j2); if(j<j2&&flag[i][j+1]==0&&a[i][j+1]==x) find(x,i,j+1,i1,i2,j1,j2); if(i>i1&&flag[i-1][j]==0&&a[i-1][j]==x) find(x,i-1,j,i1,i2,j1,j2); if(j>j1&&flag[i][j-1]==0&&a[i][j-1]==x) find(x,i,j-1,i1,i2,j1,j2); return; } int pcl(int i1,int i2,int j1,int j2) { memset(c,0,sizeof(c)); memset(flag,0,sizeof(flag)); memset(color,0,sizeof(color)); int numm=0; for(int i=i1;i<=i2;i++) for(int j=j1;j<=j2;j++) if(flag[i][j]==0) { if(color[a[i][j]]==0) numm++,c[numm]=a[i][j]; if(numm>2) return 0; color[a[i][j]]++; find(a[i][j],i,j,i1,i2,j1,j2); } if((color[c[1]]==1&&color[c[2]]>1)||(color[c[2]]==1&&color[c[1]]>1)) return 1; else return 0; } int check(int x) { for(int i=1;i<=num;i++) if(i!=x&&pcl_[x].i1>=pcl_[i].i1&&pcl_[x].i2<=pcl_[i].i2&&pcl_[x].j1>=pcl_[i].j1&&pcl_[x].j2<=pcl_[i].j2) return 0; return 1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { char x; cin>>x; a[i][j]=x-'A'; } for(int i1=1;i1<=n;i1++) for(int i2=i1;i2<=n;i2++) for(int j1=1;j1<=n;j1++) for(int j2=j1;j2<=n;j2++) if(pcl(i1,i2,j1,j2)==1) { num++; pcl_[num].i1=i1; pcl_[num].i2=i2; pcl_[num].j1=j1; pcl_[num].j2=j2; } for(int i=1;i<=num;i++) if(check(i)==1) ans++; cout<<ans; }

详情