100 #P3140. [HNOI2013] 消毒
[HNOI2013] 消毒
[HNOI2013] 消毒
题目描述
生物实验室里,小 T 有一个尺寸为 的长方体实验皿。实验皿被分为 个单位立方体,分别用 表示,其中 、、。导师要求小 T 给其中指定的单位立方体消毒。
每次操作可以选一个由连续的单位立方体组成、各边沿实验皿坐标轴的长方体区域。若该区域的尺寸为 ,消毒要用 单位的 F 试剂。可以给同一个单位立方体消毒多次,也可以覆盖无需消毒的单位立方体。
求覆盖所有指定的单位立方体最少要用多少单位的 F 试剂。
输入格式
第一行是一个正整数 ,表示数据组数。
每组数据的第一行是三个正整数 ,表示实验皿的尺寸。
接下来依次给出 个矩阵,每个矩阵有 行 列,元素用空格分隔。第 个矩阵的第 行第 列为 ,表示 需要消毒,为 则表示无需消毒。
输出格式
对每组数据输出一行一个整数,表示最少需要的 F 试剂用量。
样例
1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
3
从 到 的长方体需要 单位试剂,从 到 的长方体需要 单位试剂。两次消毒覆盖了所有指定的单位立方体。
数据范围
, 均为正整数,且 。
相关
在下列比赛中: