B21 习题-1 取糖果

题目描述

给出 $n\times m$ 的棋盘里，有些格子放着一些糖果，有些格子没有糖果。 佩奇打算从棋盘中，孤立的糖果堆中，每堆取走 $k$ 颗（如果不够 $k$ 颗则全部取走）。 孤立的定义：某堆糖果横向和纵向的相邻格子里都没有糖果（若某堆糖果在棋盘的边、角位置，则只考虑棋盘内的横向和纵向的相邻格子）。 请问，佩奇最终能够取得多少颗糖果？

输入格式

共 $n+1$ 行： 第一行三个正整数 $m,n,k$ ，分别表示矩阵的列、行数以及每次取糖果的最大数量； 接下来的 $n$ 行，每行 $m$ 个正整数，描述初始状态下糖果的摆放情况，第 $i$ 行 $j$ 列的格子有 $a_{i,j}$ 颗糖。

输出格式

一行一个整数，表示佩奇最终取走的糖果数量。

样例输入

4 4 5
9 3 0 0
0 0 6 0
1 0 0 0
0 0 0 8

样例输出

11

样例分析

孤立的糖果堆有三个，坐标分别为 $(2,3),(3,1),(4,4)$ ，所以佩奇可以取得的糖果为 $5+1+5=11$。

数据范围

对于 $100\%$ 的数据： $3 \le n,m \le 1000$，$0 \le k,a_{i,j}\le 5000$ 。