bzoj:1675 [Usaco2005 Feb]Rigging the Bovine Election 竞选划区

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?

农场被划分为5x5的格子，每个格子中都有一头奶牛，并且只有荷斯坦(标记为H)和杰尔西（标记为J）两个品种．如果一头奶牛在另一头上下左右四个格子中的任一格里，我们说它们相连．奶牛要大选了．现在有一只杰尔西奶牛们想选择7头相连的奶牛，划成一个竞选区，使得其中它们品种的奶牛比荷斯坦的多．要求你编写一个程序求出方案总数．

Input

* Lines 1..5: Each of the five lines contains five characters per line, each 'H' or 'J'. No spaces are present.

5行，输入农场的情况．

Output

* Line 1: The number of distinct districts of 7 connected cows such that the Jerseys outnumber the Holsteins in the district.

输出划区方案总数．

Sample Input

HHHHH
JHJHJ
HHHHH
HJHHJ
HHHHH

Sample Output

HINT

bzoj:1675 [Usaco2005 Feb]Rigging the Bovine Election 竞选划区

usaco良心网站，直接暴力不会挂……233

暴力枚举点就行了，每次枚举就在已经选到的点周围选就行咯，随手带几个剪枝。

至于去重，直接hash就好。在累计答案处hash：64MS，每一层搜索都hash（去掉重复扩展的状态）20MS，玩火人工二分MOD:44MS、48MS……

运气#1

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MOD=;

int ans=,xx,yy,k;

int hash[MOD];

char c[][];

void dfs(int x,int y,int hn,int jn,int p){

    if (x<||y<||x>||y>) return;

    if (x<xx||(x==xx&&y<yy)) return;

    if (c[x][y]=='H') hn++;else jn++;

    if (hn>) return;

    p+=<<((x*+y));

    k=p%MOD;

    while(hash[k]!=-){

        if (hash[k]==p) return;

        k++;

        if (k>=MOD) k-=MOD;

    }

    hash[k]=p;

    if (hn+jn==){

        ans++;

        return;

    }

    char s=c[x][y];

    c[x][y]=;

    for (int i=;i<;i++)

    for (int j=;j<;j++)

    if (c[i][j]==){

        if (c[i+][j]!=) dfs(i+,j,hn,jn,p);

        if (c[i-][j]!=) dfs(i-,j,hn,jn,p);

        if (c[i][j+]!=) dfs(i,j+,hn,jn,p);

        if (c[i][j-]!=) dfs(i,j-,hn,jn,p);

    }

    c[x][y]=s;

}

int main(){

    for (int i=;i<;i++) scanf("%s",c[i]);

    memset(hash,-,sizeof(hash));

    for (xx=;xx<;xx++)

    for (yy=;yy<;yy++) dfs(xx,yy,,,);

    printf("%d\n",ans);

}