P1671 Rigging the Bovine Election S 【洛谷算法习题】

P1671 Rigging the Bovine Election S

网页链接

P1671 Rigging the Bovine Election S

题目描述

农场被划分为

5

×

5

5\\times 5

5×5 的格子，每个格子中都有一头奶牛，并且只有荷斯坦（标记为 H）和杰西（标记为 J）两个品种。如果一头奶牛在另一头上下左右四个格子中的任一格里，我们说它们相连。奶牛要大选了。现在杰西奶牛们想选择

7

7

7 头相连的奶牛，划成一个竞选区，使得其中它们品种的奶牛比荷斯坦的多。

要求你编写一个程序求出方案总数。

输入格式

5

5

5 行，表示农场的情况。

输出格式

输出划区方案总数。

输入输出样例 #1

输入 #1

HHHHH
JHJHJ
HHHHH
HJHHJ
HHHHH

输出 #1

2

解题思路

本题是组合枚举 + 连通性检查的搜索题。农场为

5

×

5

5\\times5

5×5 的网格，共

25

25

25 个格子，需要从中选出

7

7

7 个格子组成一个竞选区，要求这

7

7

7 个格子连通，并且其中杰西奶牛（J）的数量不少于

4

4

4。由于

25

25

25 选

7

7

7 的组合数只有

C

25

7

=

480700

C_{25}^7 = 480700

C257​=480700，可以直接枚举所有组合并逐一检验。

1. 问题等价转化

• 将 $5\times 5$
• 从 $25$
• 对于每个组合，需要判断：
  • 这 $7$
  • 其中字符为 J 的格子数量是否 $\ge 4$
• 满足上述条件的组合计数即为答案。

2. 算法实现

3. 复杂度分析

• 时间复杂度：枚举 $C_{25}^7\approx 4.8\times 10^5$
• 空间复杂度：仅需存储地图、当前组合的坐标数组、访问标记数组等，均为常数级或 $O(7)$

总结

利用

25

25

25 格选

7

7

7 格组合数较小的特点，直接枚举所有可能的格子组合，并通过 DFS 检查连通性和品种数量条件。方法简单直观，足以在时限内求出方案总数。

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

const ll r=7;
const ll f[4][2]={{1,0},{0,1},{–1,0},{0,–1}};
char mp[8][8];
ll ans,t,c[8],d[8],vis[8];

void dfs1(ll k)
{
vis[k]=1; t++;
for(ll i=0;i<4;i++)
{
ll nx=c[k]+f[i][0];
ll ny=d[k]+f[i][1];
for(ll j=1;j<=r;j++)
if(c[j]==nx && d[j]==ny && !vis[j]) dfs1(j);
}
}

void dfs2(ll x,ll y)
{
if(y==r+1)
{
ll sum=0; t=0;
memset(vis,0,sizeof(vis));
for(ll i=1;i<=r;i++) if(mp[c[i]][d[i]]=='J') sum++;
dfs1(1);
if(sum>=4 && t==r) ans++;
return;
}
if(x>25) return;
for(ll i=x;i<=25;i++)
{
c[y]=(i+4)/5;
d[y]=i–((i+4)/5–1)*5;
dfs2(i+1,y+1);
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(ll i=1;i<=5;i++)
for(ll j=1;j<=5;j++)
cin>>mp[i][j];
dfs2(1,1);
cout<<ans<<endl;
return 0;
}