P1861 星之器

    • 22通过
    • 44提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Magic Land 上的时间又过了若干世纪„„

    现在, 人们谈论着一个传说:从前,他们的祖先来到了一个位于东方的岛屿, 那里简直就是另外一个世界。善于分析与构造的 Magic Land 上的人们总是不明 白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。

    题目描述

    偶然地,一个魔法使(Magician)来到了Magic Land,在临走的时候留下了 一个神奇的盒子,叫做星之器(Casket of star)。 虽然不知道这个盒子是做什么的,但是经过了大量的实验和计算后,人们已 经清楚它的一些事实:

    1.星之器之中有N×M 个区域,可看作分成 N行和 M列的格子,每个区域之中有若干单位的称为“星”的对象,这个对象的最小单位已经被确定,所以,这个数量总是整数。

    2.魔法使可以驱动星之器中位于同一行或同一列的不相邻(有公共边的区域称为相邻的)两个区域中各 1 单位的“星”,使得它们分别向中心移动 1 格。

    3.每一次使用2 中的方法驱动“星”,将会产生魔力,魔法使会得到这一部分魔力。魔力的量等于这个两个区域之间所间隔的区域数。

    这样,我们可以用一个 N×M 的数表来表示星之器的状态,比如 N=2,M=3 时:

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

    当星之器为左图的状态时,通过操纵第一行的第 1 和3 个区域中的“星” (加粗的数字对应的区域),变为右图所示的状态,同时,将产生 1 单位的魔力(因 为这两个区域之间恰好隔了 1 个区域)。

    在经过了进一步的研究之后,人们知道了这个星之器最初的状态(Ini)以及最终被他们得到时的状态(Fin)。

    你希望知道,星之器最多帮助它的拥有者提供了多少的魔力。即:经过一系列上述操作由初态(Ini)变为终态(Fin) ,至多产生多少魔力。

    需要注意的是,显然操作过程中每个区域内“星”的数量不能是负的,即:如果那个区域已经没有“星”了,当然就不能继续操作了。

    输入输出格式

    输入格式:

    第一行包含两个正整数N、M 表示星之器的大小。

    接下来的N 行,每行包含 M个自然数:Iniij,描绘了初态(Ini)。

    在一个空行后的N 行,每行包含 M 个自然数:Fin ,描绘了终态(Fin) 。

    输出格式:

    输出一个正整数,表示至多产生的魔力。

    输入输出样例

    输入样例#1: 复制
    5 5 
    1 0 0 0 1 
    0 0 0 0 0 
    0 0 0 0 0 
    0 1 0 1 1 
    1 0 0 0 0 
    
    0 0 0 0 0 
    0 0 0 0 1 
    2 0 0 0 1 
    0 0 2 0 0 
    0 0 0 0 0
    输出样例#1: 复制
    7

    说明

    100%的数据中1 ≤ N,M ≤ 200,Iniij,Finij ≤ 1000。

    所有数据保证了至少存在一个操作方法使得星之器由初态变为终态,同时保 证了初态与终态不是完全相同的。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。