蓝桥云课 剪格子

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

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

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

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

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

输入描述

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

接下来是 nn 行，每行 mm 个正整数，用空格分开。每个整数不大于 10^410
4
。

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

解题思路：输入时用sum记下矩阵所有数的和，然后用dfs走，每次把走到的点加到s里，每次dfs是判断s==sum/2,等于了就说明这样分割可以，但题目说了要最小数目，所以取对q，c取min。

代码如下：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum=0,q=10000;
int a[15][15];
int b[15][15];
int fx[4][4]={{0,1},{1,0},{-1,0},{0,-1}};//四个方向
void dfs(int x,int y,int s,int c){if(s==sum/2){q=min(q,c);//对q，c取最小的return ;}for(int k=0;k<4;k++){int i,j;i=x+fx[k][0];j=y+fx[k][1];if(i<1||j<1||j>m||i>n||b[i][j]) continue;b[i][j]=1;dfs(i,j,s+a[i][j],c+1);//a[i][j]可以走，给s加a[i][j],次数c加一b[i][j]=0;}
}
int main()
{cin>>m>>n;memset(b,0,sizeof b);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];sum+=a[i][j];//记下矩阵所有数的和}}//cout<<sum;dfs(1,1,a[1][1],1);//从第一个格子出发cout<<q;return 0;
}