剪格子 （C语言代码）

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




注意事项:





参考代码:

#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;

}