剪格子  

Description

 

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

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

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

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

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

 

Input

 

程序先读入两个整数 m n 用空格分割 (m,n<10)。

表示表格的宽度和高度。

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

 

Output

 

输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。

 

代码

https://blog.csdn.net/qq_36238595/article/details/55670334

#include<iostream>

using namespace std;

int m, n;
int sum=0;
int a[15][15];
bool vis[15][15] = { 0 };
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
bool flag = 0;

void dfs(int x, int y, int ss, int cnt) {
    if (flag)
        return;
    if (ss == sum / 2) {
        cout << cnt << endl;
        flag = 1;
        return;
    }
    if (ss > sum / 2)
        return;
    int xx, yy;
    vis[x][y] = 1;
    ss += a[x][y];
    for (int i = 0;i < 4;i++) {
        xx = dir[i][0] + x;
        yy = dir[i][1] + y;
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy]) {
            vis[xx][yy] = 1;
            dfs(xx, yy, ss, cnt + 1);
            vis[xx][yy] = 0;
        }
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> a[i][j];
            sum += a[i][j];
        }
    }
    if (sum % 2 != 0) {
        cout << 0 << endl;
    }
    else {
        dfs(0, 0, 0, 0);
    }
    return 0;
}