深圳幻海软件技术有限公司 欢迎您！
更多

蓝桥杯带刷，带刷！！！

2023-04-26

int for long
A:::::::::::::::::::::::::::::::::::m计划（双指针，滑动窗口，倍增）题目描述小明是个鹅卵石收藏者，从小到大他一共收藏了 nn 块鹅卵石，编号分别为1∼n，价值分别为a1​，a2​，⋯,an​。这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所

A:::::::::::::::::::::::::::::::::::m计划（双指针，滑动窗口，倍增）

题目描述

小明是个鹅卵石收藏者，从小到大他一共收藏了 nn 块鹅卵石，编号分别为 1∼n，价值分别为 a1​，a2​，⋯,an​。

这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。

很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。

小明制定了一套名为m计划的选择方案，其内容如下：

  • 对于任意区间 [i,i + m - 1]丢弃价值最小的鹅卵石i∈[1,n−m+1]。
  • 对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。

请你输出将被小明丢弃的鹅卵石的价值。

输入描述

输入第 1 行包含两个正整数 n,m。

接下来一行包含 n 个正整 a1​,a2​,⋯,an​，表示鹅卵石的价值。

1≤m≤n≤5×10的5次方，0≤ai​≤10的9次方。

输出描述

输出共 n−m+1 行，每行输出一个整数，第 i 行输出整数的含义为 ai​,ai+1​,⋯,ai+m−1​ 的最小值。

输入输出样例

示例 1

输入

  1. 5 3
  2. 5 3 2 4 1

输出

  1. 2
  2. 2
  3. 1

  1. #include <iostream>
  2. using namespace std;
  3. int n,m;
  4. int a[500005];
  5. struct node{
  6. int xiabiao;
  7. int min1;
  8. };
  9. node check1(int x,int y){
  10. node ans1;
  11. ans1.xiabiao=0;
  12. ans1.min1=1000000;
  13. for(int i=x;i<=y;i++){
  14. if(a[i]<=ans1.min1){
  15. ans1.min1=a[i];
  16. ans1.xiabiao=i;
  17. }
  18. }
  19. return ans1;
  20. }
  21.  
  22. bool check2(int l,int r,int x){
  23. return x>=l&&x<=r;
  24. }
  25.  
  26.  
  27. int main(){
  28. cin>>n>>m;
  29. for(int i=1;i<=n;i++){
  30. cin>>a[i];
  31. }
  32. node mm=check1(1,m);
  33. int l=2,r=m+1;
  34. cout<<mm.min1<<endl;
  35. while(r<=n){
  36. if(check2(l,r,mm.xiabiao)){
  37. if(mm.min1>=a[r]){
  38. mm.min1=a[r];
  39. mm.xiabiao=r;
  40. }
  41. }else{
  42. mm=check1(l,r);
  43. }
  44. cout<<mm.min1<<endl;
  45. r++;
  46. l++;
  47. }
  49. return 0;
  50. }

B:::::::::::::::::::::::::::::::::::长草（BFS）

题目描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，

这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

输入描述

输入的第一行包含两个整数 n,m。

接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。

接下来包含一个整数 k。 其中，2≤n,m≤1000，1≤k≤1000。

输出描述

输出 n 行，每行包含 mm 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

输入输出样例

示例

输入

  1. 4 5
  2. .g...
  3. .....
  4. ..g..
  5. .....
  6. 2

输出

  1. gggg.
  2. gggg.
  3. ggggg
  4. .ggg.

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int n,m,k;
  5. char a[1005][1005];
  6. struct node{
  7. int x,y;
  8. int su;
  9. node(int xx,int yy,int suu){
  10. x=xx;
  11. y=yy;
  12. su=suu;
  13. }
  14. };
  15. queue<node> h;
  16. bool check(int x,int y){
  17. return x>=1&&x<=n&&y>=1&&y<=m; 
  18. } 
  19. int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
  20. int main(){
  21. cin>>n>>m;
  22. for(int i=1;i<=n;i++){
  23. for(int j=1;j<=m;j++){
  24. cin>>a[i][j];
  25. if(a[i][j]=='g'){
  26. h.push(node(i,j,0));
  27. }
  28. } 
  29. }
  30. cin>>k;
  31. while(!h.empty()){
  32. node j=h.front();
  33. h.pop();
  34. for(int i=0;i<4;i++){
  35. int tx=j.x+f[i][0];
  36. int ty=j.y+f[i][1];
  37. if(check(tx,ty) && a[tx][ty]=='.' && j.su+1<=k){
  38. a[tx][ty]='g';
  39. h.push(node(tx,ty,j.su+1));
  40. }
  41. }
  42. }
  43. for(int i=1;i<=n;i++){
  44. for(int j=1;j<=m;j++){
  45. cout<<a[i][j];
  46. }
  47. cout<<endl;
  48. }
  49. return 0;
  50. }

C:::::::::::::::::::::::::::::::::::带分数（全排列）

题目描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。

类似这样的带分数，100 有 11 种表示法。

输入描述

从标准输入读入一个正整数  (N<1000×1000)。

输出描述

程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

输入输出样例

示例

输入

100

输出

11

运行限制

  • 最大运行时间：3s
  • 最大运行内存: 64M
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n;
  5. long long ans;
  6. int a[9]={1,2,3,4,5,6,7,8,9};
  7. int he(int l,int r){
  8. int ans1=0;
  9. for(int i=l;i<=r;i++){
  10. ans1=ans1*10+a[i];
  11. }
  12. return ans1;
  13. }
  14. int main(){
  15. cin>>n;
  16. while(next_permutation(a,a+9)){
  17. for(int i=0;i<7;i++){
  18. for(int j=i+1;j<8;j++){
  19. int a=he(0,i);
  20. int b=he(i+1,j);
  21. int c=he(j+1,8);
  22. if(a*c+b==n*c){
  23. ans++;
  24. }
  25. }
  26. }
  27. }
  28. cout<<ans; 
  29. return 0;
  30. }

 D:::::::::::::::::::::::::::::::::::合根植物（并查集）

题目描述

w 星球的一个种植园，被分成 m×n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入描述

第一行，两个整数 m,n，用空格分开，表示格子的行数、列数（1≤m,n≤1000）。

接下来一行，一个整数 k (0≤k≤105 )，表示下面还有 k 行数据。

接下来 k 行，每行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5×4 的小格子，编号：

  1. 1 2 3 4
  2. 5 6 7 8
  3. 9 10 11 12
  4. 13 14 15 16
  5. 17 18 19 20

输出描述

输出植物数量。

输入输出样例

示例

输入

  1. 5 4
  2. 16
  3. 2 3
  4. 1 5
  5. 5 9
  6. 4 8
  7. 7 8
  8. 9 10
  9. 10 11
  10. 11 12
  11. 10 14
  12. 12 16
  13. 14 18
  14. 17 18
  15. 15 19
  16. 19 20
  17. 9 13
  18. 13 17

输出

5

样例说明

其合根情况参考下图：

运行限制

  • 最大运行时间：2s
  • 最大运行内存: 256M
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int m,n,k;
  5. int vis[1000005];
  6. int fa[1000005];
  7. int find(int x){
  8. if(fa[x]==x) return x;
  9. return fa[x]=find(fa[x]);
  10. }
  11. int ans;
  12. void jiaru(int x,int y){
  13. int tx=find(x);
  14. int ty=find(y);
  15. if(tx!=ty){
  16. fa[tx]=ty;
  17. }
  18. }
  19. int main(){
  20. cin>>m>>n>>k;
  21. for(int i=0;i<=n*m;i++){
  22. fa[i]=i;
  23. }
  24. for(int i=0;i<k;i++){
  25. int a,b;
  26. cin>>a>>b;
  27. jiaru(a,b);
  28. }
  29. for(int i=1;i<=n*m;i++){
  30. vis[find(i)]=1;
  31. }
  32. for(int i=1;i<=n*m;i++){
  33. if(vis[i]){
  34. ans+=1;
  35. }
  36. }
  37. cout<<ans; 
  38. return 0;
  39. }

 E:::::::::::::::::::::::::::::::::::修建公路(最小生成树，并查集)

题目描述

LL 城一共有 N 个小区。

小明是城市建设的规划者，他计划在城市修 M 条路，每修建一条路都要支付工人们相应的工钱（需要支付的工钱 = 路的长度）。

然而小明所拿到的经费并不够支付修建 M 条路的工钱，于是迫于无奈，他只能将计划改变为修建若干条路，使得 N 个小区之间两两联通。

小明希望尽量剩下更多的经费投入到别的项目中，因此请你通过程序帮他计算出完成计划所需的最低开销。

输入描述

输入第一行包含三个正整数N,M。

第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。

输出描述

输出占一行，包含一个整数，表示完成计划所需的最低开销。

若无法完成计划，则输出 -1−1。

输入输出样例

示例 1

输入

  1. 5 6
  2. 1 2 2
  3. 1 3 7
  4. 1 4 6
  5. 2 3 1
  6. 3 4 3
  7. 3 5 2

输出

8

运行限制

  • 最大运行时间：3s
  • 最大运行内存: 256M、
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n,m;
  5. int fa[100005];
  6. int find(int x){
  7. if(fa[x]==x) return x;
  8. return fa[x]=find(fa[x]);
  9. }
  10. struct node{
  11. int qi,zhong;
  12. int juli;
  13. };
  14. bool cmp(node x,node y){
  15. return x.juli<y.juli;
  16. }
  17.  
  18. long long ans;
  19. node g[300005];
  20. int main(){
  21. cin>>n>>m;   //n个城市，m个规划
  22. for(int i=1;i<=n;i++){
  23. fa[i]=i;
  24. }
  25. for(int i=1;i<=m;i++){
  26. cin>>g[i].qi>>g[i].zhong>>g[i].juli;
  27. }
  28. sort(g+1,g+m+1,cmp);
  29. for(int i=1;i<=m;i++){
  30. int tx=find(g[i].qi);
  31. int ty=find(g[i].zhong);
  32. if(tx!=ty){
  33. ans+=g[i].juli;
  34. fa[tx]=ty;
  35. }
  36. }
  37. int w=find(1);
  38. for(int i=1;i<=n;i++){
  39. if(w!=find(i)){
  40. cout<<-1;
  41. return 0;
  42. }
  43. }
  44. cout<<ans;
  45. return 0;
  46. }

 F:::::::::::::::::::::::::::::::::::小明的背包2（完全背包）

题目描述

小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有 N 种物品，第 ii 种物品的体积为 wi​，价值为 vi​，每种物品都有无限多个。

小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数w,v，表示物品的体积和价值。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

  1. 5 20
  2. 1 6
  3. 2 5
  4. 3 8
  5. 5 15
  6. 3 3

输出

120

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. int n,v;
  5. int wi[1005];
  6. int vi[1005];
  7. int dp[1005][1005];
  8. int main(){
  9. cin>>n>>v;
  10. for(int i=1;i<=n;i++){
  11. cin>>wi[i]>>vi[i];  //体积和价值 
  12. }
  13. for(int i=1;i<=n;i++){
  14. for(int j=1;j<=v;j++){
  15. dp[i][j]=dp[i-1][j];
  16. if(j>=wi[i]){
  17. dp[i][j]=max(dp[i-1][j],dp[i][j-wi[i]]+vi[i]);
  18. }
  19. }
  20. }
  21. cout<<dp[n][v];
  22. return 0;
  23. }

 G:::::::::::::::::::::::::::::::::::作物杂交（搜索）

题目描述

作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N)，第 i 种作物从播种到成熟的时间为 Ti​。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。

初始时，拥有其中 M 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：

第 1 天到第 7 天 (作物 B 的时间)，A × B → C。

第 8 天到第 12 天 (作物 A 的时间)，A × C → D。

花费 12 天得到作物 D 的种子。

输入描述

输入的第 1 行包含 4 个整数 N,M,K,T，NN 表示作物种类总数 (编号 1 至 N)，MM 表示初始拥有的作物种子类型数量，KK 表示可以杂交的方案数，TT 表示目标种子的编号。

第 2 行包含 N 个整数，其中第 ii 个整数表示第 ii 种作物的种植时间 Ti​ (1≤Ti​≤100)。

第 3 行包含 M 个整数，分别表示已拥有的种子类型 (1≤Kj​≤M)，Kj​ 两两不同。

第 4 至 K + 3 行，每行包含 3 个整数 A,B,C，表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。

其中，1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N, 保证目标种子一定可以通过杂交得到。

输出描述

输出一个整数，表示得到目标种子的最短杂交时间。

输入输出样例

示例

输入

  1. 6 2 4 6
  2. 5 3 4 6 4 9
  3. 1 2
  4. 1 2 3
  5. 1 3 4
  6. 2 3 5
  7. 4 5 6

输出

16

样例说明

第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。

第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。

第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。

第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。

总共花费 16 天。

运行限制

语言最大运行时间最大运行内存
C++2s256M
C2s256M
Java3s256M
Python310s256M
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn=0x3f3f3f3f;
  5. int tim[2010];
  6. int dp[2010]; 
  7. vector<pair<int, int> > zajiao[2010]; 
  8. int f(int n){
  9. if (dp[n]!=maxn) return dp[n];
  10. for (int i=0;i<zajiao[n].size();++i){
  11. int a=zajiao[n][i].first,b=zajiao[n][i].second;
  12. int tmp = max(f(a), f(b))+max(tim[a],tim[b]);
  13. dp[n]=min(dp[n],tmp);
  14. } 
  15. return dp[n];
  16. }
  17. int main(){
  18. for (int i=0;i<2010;i++){
  19. dp[i]=maxn;
  20. }
  21. int n,m,k,t;
  22. cin>>n>>m>>k>>t;
  23. for (int i=1;i<=n;++i){
  24. cin>>tim[i];
  25. }
  26. for (int i=1;i<=m;++i){
  27. int j;
  28. cin>>j;
  29. dp[j]=0;
  30. }
  31. for (int i=1;i<=k;++i){
  32. int a,b,c;
  33. cin>>a>>b>>c;
  34. zajiao[c].push_back(make_pair(a, b));
  35. }
  36. f(t);
  37. cout<<dp[t]<<endl;
  38. return 0; 
  39. }

 H:::::::::::::::::::::::::::::::::::序列求和(DFS，唯一分解定理)

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 tt，总是可以找到含有 tt 个约数的整数。小明对于含有 tt 个约数的最小数非常感兴趣，并把它定义为 S_tSt​ 。

例如S1​=1,S2​=2,S3​=4,S4​=6，⋅⋅⋅ 。

现在小明想知道，前 60 个 Si​ 的和是多少？即 S1​+S2​+⋅⋅⋅+S60​ 是多少？

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. vector<long long> m;
  6. int su[100000];
  7. bool check(long long x){
  8. if(x==1){
  9. return false;
  10. }
  11. if(x==2){
  12. return true;
  13. }
  14. for(int i=2;i*i<=x;i++){
  15. if(x%i==0){
  16. return false;
  17. }
  18. }
  19. return  true;
  20. }
  21. long long pow1(long long a,long long b){
  22. long long ans=1;
  23. while(b){
  24. if(b&1) ans=ans*a;
  25. b/=2;
  26. a*=a;
  27. }
  28. return ans;
  29. }
  30. long long ans;
  31. long long res1=1e18;
  32. long long dfs(long long x,vector<long long>g) 
  33. {
  34. if(check(x)||x==1)return pow1(2,x-1); 
  35. for(long long i=2;i*i<=x;i++)
  36. {
  37. if(x%i==0)
  38. {
  39. long long t=x/i;
  40. g.push_back(i);
  42.  
  43. vector<long long>tmp=g;
  44. tmp.push_back(t); 
  45. sort(tmp.begin(),tmp.end(),greater<long long>());
  46. long long s=1;
  47. for(int j=0;j<tmp.size();j++)
  48. s*=pow1(su[j],tmp[j]-1);
  49. res1=min(res1,s);
  51. dfs(t,g);
  52. g.pop_back();
  53. }
  54. }
  55. return res1;
  56. }
  57. int main(){
  58. int cc=0;
  59. for(int i=2;i<=100000;i++){
  60. if(check(i)){
  61. su[cc]=i;
  62. cc++;
  63. }
  64. }
  65. ans=1+2+4+6;
  66. for(int i=5;i<=60;i++){
  67. res1=1e18;
  68. m.clear();
  69. long long ans1=dfs(i,m);
  70. ans+=ans1;
  71. }
  72. cout<<ans;
  73. return 0;
  74. }

  I:::::::::::::::::::::::::::::::::::青蛙跳杯子（BFS）

题目描述

XX 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

XX 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

∗WWWBBB

其中，W 字母表示白色青蛙，B 表示黑色青蛙，*∗ 表示空杯子。

X 星的青蛙很有些癖好，它们只做 3 个动作之一：

  1. 跳到相邻的空杯子里。

  2. 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。

  3. 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上图的局面，只要 1 步，就可跳成下图局面：

WWW∗BBB

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入描述

输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。

输出描述

输出要求为一个整数，表示至少需要多少步的青蛙跳。

输入输出样例

示例

输入

  1. *WWBB
  2. WWBB*

输出

2

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <map>
  5. using namespace std;
  6. string a,b;
  7. struct node{
  8. string a;
  9. int bu;
  10. int x;
  11. node(string aa,int buu,int xu){
  12. a=aa;
  13. bu=buu;
  14. x=xu;
  15. }
  16. };
  17. string jiaohuan(string a,int x,int y){
  18. char m=a[x];
  19. a[x]=a[y];
  20. a[y]=m;
  21. return a;
  22. }
  23. map<string,bool> kk;
  24. queue<node> q;
  25. bool check(int x){
  26. return x>=0 && x<a.size();
  27. }
  28. int f[6]={1,-1,2,-2,3,-3};
  29. int main(){
  30. cin>>a>>b;
  31. int c=0;
  32. for(int i=0;i<a.size();i++){
  33. if(a[i]=='*'){
  34. c=i;
  35. }
  36. }
  37. kk[a]=1;
  38. q.push(node(a,0,c)); 
  39. while(!q.empty()){
  40. node t=q.front();
  41. q.pop();
  42.  
  43. if(t.a==b){
  44. cout<<t.bu;
  45. break;
  46. }
  47.  
  48. for(int i=0;i<6;i++){
  49. int tx=t.x+f[i];
  50. string xx=jiaohuan(t.a,t.x,tx);
  51. if(check(tx) && !kk[xx]){
  52. kk[xx]=1;
  53. q.push(node(xx,t.bu+1,tx));
  54. }
  55. }
  56. }
  57. return 0;
  58. }

   J:::::::::::::::::::::::::::::::::::剪格子（DFS）

题目描述

如下图所示，3 x 3 的格子中填写了一些整数。

我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 60。

本题的要求就是请你编程判定：对给定的 m×n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入描述

输入描述

程序先读入两个整数 m,n 用空格分割 (m,n<10)，表示表格的宽度和高度。

接下来是 n 行，每行 m 个正整数，用空格分开。每个整数不大于 104。

输出描述

在所有解中，包含左上角的分割区可能包含的最小的格子数目。

输入输出样例

示例

输入

  1. 3 3
  2. 10 1 52
  3. 20 30 1
  4. 1 2 3

输出

3

运行限制

  • 最大运行时间：5s
  • 最大运行内存: 64M
  1. #include <iostream>
  2. using namespace std;
  3. int a[15][15];
  4. int n,m;
  5. int sum;
  6. int he;
  7. int ans=1e9;
  8. bool vis[15][15];
  9. int aa[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
  10. bool check(int x,int y){
  11. return x>=0&&x<=n&&y>=0&&y<=m;
  12. }
  13. void dfs(int x,int y,int g){
  14. if(g>=ans){
  15. return;
  16. }
  17. if(he==sum/2){
  18. ans=min(ans,g);
  19. }
  20. for(int i=0;i<4;i++){
  21. int tx=x+aa[i][0];
  22. int ty=y+aa[i][1];
  23. if(check(tx,ty) && !vis[tx][ty]){
  24. vis[tx][ty]=1;
  25. he+=a[tx][ty];
  26. dfs(tx,ty,g+1);
  27. he-=a[tx][ty];
  28. vis[tx][ty]=0;
  29. }
  30. }
  31. }
  32. int main(){
  33. cin>>m>>n;
  34. for(int i=1;i<=n;i++){
  35. for(int j=1;j<=m;j++){
  36. int x=0;
  37. cin>>x;
  38. a[i][j]=x;
  39. sum+=x;
  40. }
  41. }
  42. if(sum%2==1){
  43. cout<<0;
  44. return 0;
  45. }
  46. vis[1][1]=1;
  47. he=a[1][1];
  48. dfs(1,1,1);
  49. cout<<ans;
  50. return 0;
  51. }

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45066 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪