小宇


私信TA

用户名:582623378

访问量:6209

签 名:

等  级
排  名 3959
经  验 874
参赛次数 0
文章发表 10
年  龄 0
在职情况 学生
学  校 泰州学院
专  业

  自我简介:

解题思路:
深度优先搜索+回溯(筛选)




注意事项:





参考代码:

#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 人评分

  评论区