国家城乡和住房建设部网站首页,wordpress mysuc cms,做企业网站哪家公司好,国内什么网站用asp.net题目描述 历届试题 剪格子 时间限制#xff1a;1.0s 内存限制#xff1a;256.0MB
问题描述 如下图所示#xff0c;3 x 3 的格子中填写了一些整数。
我们沿着图中的星号线剪开#xff0c;得到两个部分#xff0c;每个部分的数字和都是60。 本题的要求就是请你编程判定1.0s 内存限制256.0MB
问题描述 如下图所示3 x 3 的格子中填写了一些整数。
我们沿着图中的星号线剪开得到两个部分每个部分的数字和都是60。 本题的要求就是请你编程判定对给定的m x n 的格子中的整数是否可以分割为两个部分使得这两个区域的数字和相等。 如果存在多种解答请输出包含左上角格子的那个区域包含的格子的最小数目。 如果无法分割则输出 0。 输入 程序先读入两个整数 m n 用空格分割 (m,n 10)。 表示表格的宽度和高度。 接下来是n行每行m个正整数用空格分开。每个整数不大于10000。 输出 输出一个整数表示在所有解中包含左上角的分割区可能包含的最小的格子数目。 样例输入
3 3 10 1 52 20 30 1 1 2 3
样例输出
3
解题思路 直接看代码注释很清楚
代码如下
#include iostream
using namespace std;
int sum 0;
int ans 99999999;
int n, m;
const int N 13;
int mp[N][N];int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};
bool vis[N][N];void dfs(int x, int y, int cnt, int sum1) {if (sum1 sum / 2) {if (cnt ans) {ans cnt;return ;}}for (int i 0; i 4; i) {int xx x dx[i], yy y dy[i];if (xx 0 xx n yy 0 yy m)if (!vis[xx][yy]) {vis[xx][yy] true;dfs(xx, yy, cnt 1, sum1 mp[xx][yy]);vis[xx][yy] false;}}
}int main() {cin m n;//注意坑点先输入列再输入行for (int i 0; i n; i)for (int j 0; j m; j) {cin mp[i][j];sum mp[i][j];}if (sum % 2)//如果总和是奇数肯定不可能可以分成相等的2份ans 0;elsedfs(0, 0, 1, mp[0][0]);//最开始一定是从左上角那块开始搜因为要包含左上角那块cout ans endl;return 0;
}
