剪格子

boyfaceone · 发表于 2013-6-24 23:40:39

如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
[attachment=388]
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是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

再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100

则程序输出：
10

(参见p2.jpg)
[attachment=389]

资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

boyfaceone · 发表于 2013-6-30 20:07:23

暂时也没想到好的算法，递归的效率实在太低了。。。

#include <string.h>
#include <stdio.h>

#define MAX_SIZE 9
#define MAX_INT 0x7FFFFFFF

#define MIN(x, y) ((x) < (y) ? (x) : (y))

int g_array[MAX_SIZE][MAX_SIZE] = {0};
int g_visit[MAX_SIZE][MAX_SIZE] = {0};
int g_row = 0;
int g_col = 0;
int g_minNum = MAX_INT;
int g_half = 0;
int g_direction[4][2] = {{-1,  0},
                         { 0,  1},
                         { 1,  0},
                         { 0, -1}};

int checkValid(int rIdx, int cIdx)
{
    if (0 > rIdx || rIdx >= g_row
     || 0 > cIdx || cIdx >= g_col)
    {
        return 0;
    }

    return 1;
}

void dfs(int rIdx, int cIdx, int sum, int num)
{
    int i;

    sum += g_array[rIdx][cIdx];

    if (sum > g_half || num + 1 > g_minNum)
    {
        return;
    }

    if (sum == g_half && 0 != g_visit[0][0])
    {
        g_minNum = MIN(g_minNum, num + 1);
        return;
    }

    for (i = 0; i < 4; i++)
    {
        int nrIdx = rIdx + g_direction[0];
        int ncIdx = cIdx + g_direction[1];

        if (checkValid(nrIdx, ncIdx)
         && 0 == g_visit[nrIdx][ncIdx]
         && sum + g_array[nrIdx][ncIdx] <= g_half)
        {
            g_visit[rIdx][cIdx] = 1;
            dfs(nrIdx, ncIdx, sum, num + 1);
            g_visit[rIdx][cIdx] = 0;
        }
    }
}

int main()
{
    int i, j;

    // 输入数字矩阵
    scanf("%d %d", &g_col, &g_row);
    for (i = 0; i < g_row; i++)
    {
        for (j = 0; j < g_col; j++)
        {
            scanf("%d", &g_array[j]);
            g_half += g_array[j];
        }
    }

    // 初步校验解是否存在
    if ((0 != (g_half & 1)) || (2 * g_array[0][0] > g_half))
    {
        printf("0\n");
        return 0;
    }

    g_half /= 2;

    for (i = 0; i < g_row; i++)
    {
        for (j = 0; j < g_col; j++)
        {
            memset(g_visit, 0, sizeof(g_visit));

            dfs(i, j, 0, 0);
        }
    }

    printf("%d\n", MAX_INT == g_minNum ? 0 : g_minNum);

    return 0;
}

		自动登录	找回密码
密码			立即注册

剪格子

浏览过的版块