题解：洛谷 P1671 [USACO05FEB] Rigging the Bovine Election S-育师

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1671 [USACO05FEB] Rigging the Bovine Election S - 洛谷

【题目描述】

农场被划分为5 × 5 5\times 55×5的格子，每个格子中都有一头奶牛，并且只有荷斯坦（标记为H）和杰西（标记为J）两个品种。如果一头奶牛在另一头上下左右四个格子中的任一格里，我们说它们相连。奶牛要大选了。现在杰西奶牛们想选择7 77头相连的奶牛，划成一个竞选区，使得其中它们品种的奶牛比荷斯坦的多。

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

【输入】

5 55行，表示农场的情况。

【输出】

输出划区方案总数。

【输入样例】

HHHHH JHJHJ HHHHH HJHHJ HHHHH

【输出样例】

【核心思想】

问题分析：给定5 × 5 5 \times 55×5的网格，每个格子为H或J。需要找出所有由7 77个相连格子组成的连通块，使得其中J的数量> 3 > 3>3（即至少4 44个）。求满足条件的连通块方案总数。这是一个DFS搜索连通块 + 去重统计问题，关键在于如何枚举所有大小为7 77的连通块并避免重复计数。
算法选择：
- DFS扩展连通块：从每个起点出发，逐步向当前连通块的相邻格子扩展，维护当前路径和J的计数
- 路径排序去重：由于同一连通块可能从不同起点、不同扩展顺序被多次发现，将路径坐标排序后转为字符串，用set自动去重
- 连通性保证：每次扩展时只能从当前已选格子的邻域中选择新格子，确保最终7 77个格子形成连通块
关键步骤：
- 读取输入：5 × 5 5 \times 55×5的字符矩阵a aa
- DFS搜索（从每个起点( i , j ) (i, j)(i,j)开始）：
  - 参数：当前坐标( x , y ) (x, y)(x,y)，J的计数c n t cntcnt，已选格子数t o t tottot
  - 将( x , y ) (x, y)(x,y)加入当前路径v vv
  - 若t o t = 7 tot = 7tot=7：
    - 若c n t > 3 cnt > 3cnt>3：将路径坐标排序后转字符串，插入set去重
    - 回溯弹出，返回
  - 标记v i s [ x ] [ y ] = 1 vis[x][y] = 1vis[x][y]=1
  - 扩展策略：遍历当前路径v vv中所有格子的四邻域，选择未访问且在界内的格子递归
  - 回溯：弹出( x , y ) (x, y)(x,y)，v i s [ x ] [ y ] = 0 vis[x][y] = 0vis[x][y]=0
- 输出st.size()
时间/空间复杂度：
- 时间复杂度：O ( 25 × C 24 6 × 7 log ⁡ 7 ) O(25 \times C_{24}^{6} \times 7 \log 7)O(25×C246×7log7)，从25 2525个起点出发，每次扩展选择相邻格子，最坏组合级复杂度，但5 × 5 5 \times 55×5网格限制实际可接受
- 空间复杂度：O ( 7 × ∣ s t ∣ ) O(7 \times |st|)O(7×∣st∣)，路径向量 + 去重集合
DFS连通块枚举的核心思想：
- 路径记录 + 排序去重：连通块是无序集合，不同搜索顺序可能产生同一连通块。将坐标排序后序列化，利用set的唯一性保证每个连通块只计数一次
- 从当前连通块扩展：每次新格子必须与已选集合中某格子相邻，而非仅从当前DFS节点扩展，这保证了连通性但增加了搜索分支
- 剪枝隐含：c n t cntcnt计数在搜索过程中自然维护，仅在t o t = 7 tot = 7tot=7时判断是否满足c n t > 3 cnt > 3cnt>3
- 适用于"网格连通块枚举 + 属性约束计数"类问题，核心是避免重复计数和保证连通性

【解题思路】

【算法标签】

#普及 #DFS-二维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义5x5的字符数组chara[10][10];// 存储字符矩阵，实际使用1-5行和1-5列boolvis[10][10];// 标记数组，记录位置是否被访问过// 定义坐标对类型typedefpair<int,int>PII;vector<PII>v;// 存储当前搜索路径上的坐标// 方向数组：上、下、左、右intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};// 使用集合存储去重后的路径字符串表示set<string>st;// 深度优先搜索函数// 参数说明：// x, y: 当前坐标// cnt: 当前路径中'J'的个数// tot: 当前路径中的位置总数voiddfs(intx,inty,intcnt,inttot){// 将当前位置加入路径v.push_back({x,y});// 如果已经选择了7个位置if(tot==7){// 检查'J'的个数是否超过3个if(cnt>3){// 创建当前路径的副本并排序vector<PII>tmp=v;sort(tmp.begin(),tmp.end());// 将排序后的路径转换为字符串string s="";for(autot:tmp){s+=to_string(t.first)+","+to_string(t.second)+";";}// 将字符串加入集合（自动去重）st.insert(s);}// 回溯：移除最后一个位置v.pop_back();return;}// 标记当前位置为已访问vis[x][y]=1;// 遍历当前路径中的所有位置for(inti=0;i<v.size();i++){intxx=v[i].first,yy=v[i].second;// 尝试四个方向for(intj=0;j<4;j++){intnx=xx+dx[j],ny=yy+dy[j];// 跳过已访问的位置if(vis[nx][ny]){continue;}// 跳过越界的位置if(nx<1||nx>5||ny<1||ny>5){continue;}// 递归搜索下一个位置// 如果新位置是'J'，则cnt+1，否则cnt不变// tot总是+1dfs(nx,ny,cnt+(a[nx][ny]=='J'),tot+1);}}// 回溯：移除当前位置，并取消标记v.pop_back();vis[x][y]=0;}intmain(){// 读入5x5的字符矩阵for(inti=1;i<=5;i++){for(intj=1;j<=5;j++){cin>>a[i][j];}}// 从每个位置开始深度优先搜索for(inti=1;i<=5;i++){for(intj=1;j<=5;j++){// 初始状态：从位置(i,j)开始// cnt初始为1如果当前位置是'J'// tot初始为1dfs(i,j,a[i][j]=='J',1);}}// 输出不同路径的数量cout<<st.size()<<endl;return0;}