TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4294
  • 题目
  • P4294E100WT与NPC问题
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    E100WT很喜欢玩RA3的旭日阵营,可是他总是把地图看成n*m的矩阵以便于城市化发展。卖完兔子的TomGuo看了他的玩法表示非常汗,一发粒子碰撞炮把他的城市摧毁殆尽,只有一些血厚的建筑还没死 (有可能全死完了)。

    E100WT需要重建他的城市,但在这之前,他需要放置一些NPC在地图上。根据地形的不同,E100WT对地图中每一块,都有一个最低的安放NPC的个数标准(表示第i行第j列的块)。他想起大爷的教诲,要让放置的NPC构成一条连通的路径,这条路径所经过的每一个块上都有满足最低标准个数的NPC或该块为建筑,最终所有建筑被路径所连通。(上下或左右两个相邻且满足条件的块即为连通,块(x,y+1)与块(x+1,y)不算相邻)

    本来E100WT会在所有格子上放满NPC,但是他发现他正在玩的这个mod里,NPC的形象都是他喜欢的动漫人物。 E100WT不想再让NPC因为自己的手残跪掉。于是他想让NPC总数最少。

    现在,他把这个NPC问题抛给了你。

    输入格式

    第一行两个整数N和M,描述矩阵数目。

    接下来N行,每行有M个空格隔开的非负整数,如果该整数为0,则该块为建筑,否则表示在该块最少需要放置的NPC个数。

    输出格式

    一个整数,表示你给出的方案中放置NPC的总个数。

    样例输入

    4 4
    0 1 1 0
    2 5 5 1
    1 5 5 1
    0 1 1 0

    样例输出

    6

    提示

    存在10%的数据 N或M = 1

    有 20% 的数据 N*M <= 10

    对于100%的数据 N,M,K <= 10, 其中k为景点数目. 输入整数都在2^16以内


    来源  EW100T