Rigging the Bovine ElectionTime Limit: 1000MS Memory Limit: 65536K Total Submissions: 1280 Accepted: 547 Description It's election time. The farm is partitioned into a 5x5 grid of cow locations, each of which holds either a Holstein ('H') or Jersey ('J') cow. The Jerseys want to create a voting district of 7 contiguous (vertically or horizontally) cow locations such that the Jerseys outnumber the Holsteins. How many ways can this be done for the supplied grid? Input * Lines 1..5: Each of the five lines contains five characters per line, each 'H' or 'J'. No spaces are present. Output * Line 1: The number of distinct districts of 7 connected cows such that the Jerseys outnumber the Holsteins in the district. Sample Input HHHHHJHJHJHHHHHHJHHJHHHHH Sample Output 2 Hint OUTPUT DETAILS: The two possible districts are: ..... ..... JHJHJ JHJHJ ....H and .H... ....J .J... ..... ..... Any other possible district with seven cows has fewer than 4 Jerseys. Source USACO 2005 February Silver好像是NOIP的奶牛选举。。。
#include <iostream> using namespace std; char a[11][11]; bool g[33292290],b[101]; int d[26],i,j,ans; void search(int t,int s,int now) { if(t>=7) { if(s>3)++ans; return; } int i,j,k; for(i=0;i<5;++i) for(j=1;j<6;++j) if((b[50+i*5+j])&&(!((b[50+(i-1)*5+j])&&(b[50+(i+1)*5+j])&& (b[50+i*5+j+1]||(j==5))&&(b[50+i*5+j-1]||(j==1))))) { b[50+i*5+j]=false; k=now|d[i*5+j]; if(g[k]) { g[k]=false; if(a[i+1][j]=='J') search(t+1,s+1,k); else search(t+1,s,k); } b[50+i*5+j]=true; } } int main() { //freopen("car.in","r",stdin); //freopen("car.out","w",stdout); for(i=1;i<6;++i,getchar()) for(j=1;j<6;++j)scanf("%c",&a[i][j]); d[1]=1; for(i=2;i<26;++i)d[i]=d[i-1]<<1; memset(g,true,sizeof(g)); memset(b,true,sizeof(b)); ans=0; for(i=0;i<5;++i) for(j=1;j<6;++j) { b[50+i*5+j]=false; g[d[i*5+j]]=false; if(a[i+1][j]=='J') search(1,1,d[i*5+j]); else search(1,0,d[i*5+j]); b[50+i*5+j]=true; } printf("%d",ans); return 0; }
