开启左侧

剪格子

二维码 [复制链接]
219 0
如图1所示,3 x 3 的格子中填写了一些整数。

剪格子图1

剪格子图1


我们沿着图中的红色线剪开,得到两个部分,每个部分的数字和都是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

(参见图2)

剪格子图2

剪格子图2



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


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

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

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

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

此例效率偏低,答案仅供参考:

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

  3. #define MAX_SIZE 9
  4. #define MAX_INT 0x7FFFFFFF

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

  6. int g_array[MAX_SIZE][MAX_SIZE] = {0};
  7. int g_visit[MAX_SIZE][MAX_SIZE] = {0};
  8. int g_row = 0;
  9. int g_col = 0;
  10. int g_minNum = MAX_INT;
  11. int g_half = 0;
  12. int g_direction[4][2] = {{-1,  0},
  13.                          { 0,  1},
  14.                          { 1,  0},
  15.                          { 0, -1}};

  16. int checkValid(int rIdx, int cIdx)
  17. {
  18.     if (0 > rIdx || rIdx >= g_row
  19.      || 0 > cIdx || cIdx >= g_col)
  20.     {
  21.         return 0;
  22.     }

  23.     return 1;
  24. }

  25. void dfs(int rIdx, int cIdx, int sum, int num)
  26. {
  27.     int i;

  28.     sum += g_array[rIdx][cIdx];

  29.     if (sum > g_half || num + 1 > g_minNum)
  30.     {
  31.         return;
  32.     }

  33.     if (sum == g_half && 0 != g_visit[0][0])
  34.     {
  35.         g_minNum = MIN(g_minNum, num + 1);
  36.         return;
  37.     }

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

  42.         if (checkValid(nrIdx, ncIdx)
  43.          && 0 == g_visit[nrIdx][ncIdx]
  44.          && sum + g_array[nrIdx][ncIdx] <= g_half)
  45.         {
  46.             g_visit[rIdx][cIdx] = 1;
  47.             dfs(nrIdx, ncIdx, sum, num + 1);
  48.             g_visit[rIdx][cIdx] = 0;
  49.         }
  50.     }
  51. }

  52. int main()
  53. {
  54.     int i, j;

  55.     // 输入数字矩阵
  56.     scanf("%d %d", &g_col, &g_row);
  57.     for (i = 0; i < g_row; i++)
  58.     {
  59.         for (j = 0; j < g_col; j++)
  60.         {
  61.             scanf("%d", &g_array[i][j]);[/i]
  62.             g_half += g_array[i][j];[/i]
  63.         }
  64.     }

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

  71.     g_half /= 2;

  72.     for (i = 0; i < g_row; i++)
  73.     {
  74.         for (j = 0; j < g_col; j++)
  75.         {
  76.             memset(g_visit, 0, sizeof(g_visit));

  77.             dfs(i, j, 0, 0);
  78.         }
  79.     }

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

  81.     return 0;
  82. }
复制代码




赞助本站





上一篇:大臣的旅费
下一篇:提取不重复的整数
学会善用【论坛搜索】功能,很多你要寻找的答案就在这里面;
如果大家发现帖子中链接有错误,请到【爱好街链接地址失效有奖报错】回帖,我们会在第一时间送上反馈的奖励!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

发新帖 回复

104

主题

104

帖子

233

街币
更多

精彩推荐

新人报到专用贴
新人报到专用贴
==新人报道格式(选填)== 【我的昵称】: 【我的性别
爱好街资源共享区文件解压密码
爱好街资源共享区文件解压密码
因本站分享的文件实在太多,目前收集整理已经接近4T,所以有些文
独立团VIP教程第1-7版全套打包下载(含课件源码工具等)
独立团VIP教程第1-7版全套打包
独立团第1版易语言教程 独立团第一版1易语言入门 1-1-1外
爱好街链接地址失效有奖报错
爱好街链接地址失效有奖报错
我们的成长离不开大家的支持!! 各位爱好街的会员:
魔鬼作坊vip教程辅助制作培训之零基础绝密汇编语言入门课程
魔鬼作坊vip教程辅助制作培训
这套课程为汇编入门教程,学习游戏逆向反汇编需要用到的基础知
万挂作坊教程+封包+E模块(全套下载)
万挂作坊教程+封包+E模块(全套
万挂-封包 封包加密解密-01 封包加密解密-02 封包加密

免责声明:
在爱好街发布的文章与主题属会员个人意见,与本站立场无关,文章内容由作者与爱好街享有相关版权,如需转载请注明出处或取得会员与本站的许可,否则本站将追究相应的法律责任,如部分内容有侵犯任何版权问题,请立即告知本站,本站将及时予以删除并致以最深的歉意。另外不得将本站内容用于商业或者非法用途,否则,一切后果请用户自负。

Mail To:MasTer@AiHaiJie.Com

快速回复
快速回复 返回顶部 返回列表