剪格子

问题描述

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

+--*--+--+
|10* 1|52|
+--****--+
|20|30* 1|
*******--+
| 1| 2| 3|
+--+--+--+

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

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

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

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

输入格式

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

表示表格的宽度和高度。

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

输出格式

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

样例输入1

3 3
10 1 52
20 30 1
1 2 3

样例输出1

样例输入2

4 3
1 1 1 1
1 30 80 2
1 1 1 100

样例输出2

深搜解决，数据比较水，没有深入去判断。其实还需要判断是否是分为两部分的，如果分为三部分就不对，而且深搜有不能解决的情况。

比如数据：

4 4

1 1 2 2

2 5 2 2

9 1 1 2

1 1 1 1

最佳情况是：

1	1	2	2
2	5	2	2
9	1	1	2
1	1	1	1

按照下面的代码无法得出最佳情况。

代码：

#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int m,n,all;
int mp[10][10];
bool vis[10][10];
int ans = inf;
void dfs(int x,int y,int sum,int c) {
    if(sum * 2 > all) return;
    if(sum * 2 == all) {
        ans = min(ans,c);
        return;
    }
    for(int i = 0;i < 4;i ++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(tx < 0 || ty < 0 || tx >= n || ty >= m || vis[tx][ty]) continue;
        vis[tx][ty] = true;
        dfs(tx,ty,sum + mp[tx][ty],c + 1);
        vis[tx][ty] = false;
    }
}
int main() {
    scanf("%d%d",&m,&n);
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < m;j ++) {
            scanf("%d",&mp[i][j]);
            all += mp[i][j];
        }
    }
    vis[0][0] = true;
    dfs(0,0,mp[0][0],1);
    if(ans == inf) ans = 0;
    printf("%d",ans);
}

新的思路是，查看所有的可能，并判断是否是分为两部分。

代码：

#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int m,n,all;
int mp[10][10];
int tag[10][10];
bool vis[10][10];
int ans = inf;
///寻找连通的且tag相同的格子个数
int get(int x,int y,int t) {
    int c = 1;
    vis[x][y] = true;
    for(int i = 0;i < 4;i ++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(tx < 0 || ty < 0 || tx >= n || ty >= m || vis[tx][ty] || tag[tx][ty] != t) continue;
        vis[tx][ty] = true;
        c += get(tx,ty,t);
    }
    return c;
}
///判断是否分为两部分，即选择两个连通域看两个的和是否是总和
bool check() {
    int x = -1,y = -1;
    memset(vis,false,sizeof(vis));
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < m;j ++) {
            if(tag[i][j] == 0) {
                x = i;
                y = j;
                break;
            }
        }
    }
    return x == -1 || get(0,0,1) + get(x,y,0) == m * n;
}
///从左往右第k个格子
void dfs(int k,int sum,int c) {
    if(sum * 2 == all) {
        if(!check()) return;
        ans = min(ans,c);
        return;
    }
    if(sum * 2 > all || k + 1 >= m * n) return;
    k ++;
    int x = k / m;
    int y = k % m;
    dfs(k,sum,c);
    tag[x][y] = 1;
    dfs(k,sum + mp[x][y],c + 1);
    tag[x][y] = 0;
}

int main() {
    scanf("%d%d",&m,&n);
    for(int i = 0;i < n;i ++) {
        for(int j = 0;j < m;j ++) {
            scanf("%d",&mp[i][j]);
            all += mp[i][j];
        }
    }
    tag[0][0] = 1;
    dfs(0,mp[0][0],1);
    if(ans == inf) ans = 0;
    printf("%d",ans);
}