C++-蓝桥杯-剪格子-[2013真题][爆搜?]

如题:

将矩阵剪成相连的两个联通块,可以有环,使得两部分权值和相等

数据范围矩阵<10x10,权值和<1000000

我寻思着觉得复杂度不对啊?自己卡个数据都会T,题目的数据太水了

dfs是错误写法,对于不满足从(1,1)开始的一笔完成的图像,就会出错

例如:

2 2

1 1

1 3

答案是:3

而普通dfs是0

总结,有思路就要写,暴力出奇迹!垃圾数据,毁我青春,败我秀发!

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int m,n,sum_c,ans=100;
 5 int c[10][10],vis[10][10];
 6 int tx[4]={1,0,0,-1};
 7 int ty[4]={0,1,-1,0};
 8 void dfs(int x,int y,int sum,int dep){
 9     if(sum>sum_c/2)return;
10     if(sum==sum_c/2){ans=min(ans,dep);return;}
11     for(int i=0;i<4;i++){
12         int x0=x+tx[i],y0=y+ty[i];
13         if(x0>=1&&x0<=n&&y0>=1&&y0<=m&&!vis[x0][y0]){
14             vis[x0][y0]=1;
15             dfs(x0,y0,sum+c[x0][y0],dep+1);
16             vis[x0][y0]=0;
17         }
18     }
19 }
20 int main(){
21     scanf("%d%d",&m,&n);
22     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[i][j]),sum_c+=c[i][j];
23     vis[1][1]=1;
24     dfs(1,1,c[1][1],1);
25     printf("%d
",ans==100?0:ans);
26     return 0;
27 } 

网络上流传的代码没有正解

不服来挑战这组数据:

5 5

1  1  1  1  1

1  10  10   10     10

1  1  1  1       10

1       10     10     10      10

1  1  1  1       75

答案应该是:16

原文地址:https://www.cnblogs.com/JasonCow/p/12404247.html