解题思路:
深度优先搜索+回溯(筛选)
注意事项:
参考代码:
#include <stdio.h>
int xmove[4]={-1,1,0,0};
int ymove[4]={0,0,-1,1};
int flag[100][100]={0};
int a[100][100]={0};
int sum=0,half,count=0,minvalue=100,m,n;
int judge(int t1,int t2)
{ if((t1>=n||t1<0)||(t2>=m||t2<0)||(sum+a[t1][t2]>half)||(flag[t1][t2]==1))
return 1;
else
return 0;
}
void back(int value,int i,int j)
{ count--;
sum-=value;
flag[i][j]=0;
}
void dfs(int value,int x,int y)
{ int i,t1,t2;
count++;
flag[x][y]=1;
sum+=value;
if(sum==half)
{
minvalue=minvalue>count?count:minvalue;
back(value,x,y);
return;
}
else
{
for(i=0;i<4;i++)
{
t1=x+xmove[i];
t2=y+ymove[i];
if(judge(t1,t2))
continue;
dfs(a[t1][t2],t1,t2);
}
back(value,x,y);
}
}
int main()
{ int i,j,num=0,max=0;
scanf("%d%d",&m,&n);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
num+=a[i][j];
if(a[i][j]>max)
max=a[i][j];
}
if(num%2!=0||max>num/2)
printf("0\n");
else
{
half=num/2;
dfs(a[0][0],0,0);
if(minvalue!=100)
printf("%d\n",minvalue);
else
printf("0\n");
}
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:733 |
简单的a+b (C语言代码)浏览:778 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:569 |
数列排序 (C语言代码)浏览:856 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1325 |
【金明的预算方案】 (C++代码)浏览:982 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:586 |
简单的a+b (C语言代码)浏览:863 |
C语言训练-亲密数 (C语言代码)浏览:691 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:620 |