logo AlgoBeat OnlineJudge
登录 注册

#215104. [语言月赛 202602] 草莓蛋糕

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

Lucia 很喜欢吃辣,但是现在她想尝试吃一次草莓蛋糕。

一个草莓蛋糕可以看成一个 列的矩阵 ,矩阵的第 行第 列会有一个参数 ,若 ,则表示这个位置有一颗草莓;否则 ,表示这个位置没有草莓。

Lucia 会以一定的位置顺序吃掉这个蛋糕。她会从第 行第 列开始向右,到第 行第 列后,再从第 行第 列开始向左,到第 行第 列,再从第 行第 列开始向右……以此类推。

比如对于一个 列的蛋糕,Lucia 吃掉的位置顺序如箭头所示:

当然 Lucia 的胃口不是很大。她会按照上述的顺序,先吃前 个位置。此时若蛋糕还没被吃完,则假设她下一个要吃的位置是第 行第 列。如果她发现这个位置恰好有草莓,即 ,那么她会继续吃 个位置;否则 ,她会停止吃蛋糕。在吃的过程中,如果蛋糕被吃完,则直接停止。

现在你需要求出,她依照上述过程,最终会吃掉多少颗草莓(即 的位置的个数)?

输入格式

第一行三个正整数 ,用半角空格隔开。

下面 行,每行 个整数。第 行第 列的数为

输出格式

一行一个正整数,即 Lucia 最终吃掉的草莓数量。

样例

样例输入 1

4 4 3
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

样例输出 1

3

样例输入 2

5 5 13
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

样例输出 2

12

样例输入 3

4 5 7
0 0 0 0 0
0 1 1 1 0
1 1 0 1 0
0 1 1 1 0

样例输出 3

6

数据范围与提示

样例解释

对于样例 1,Lucia 首先会吃掉如下红色框出的位置:

此时下一个要吃的位置是第 行第 列(即绿色框出的位置),,所以她会继续吃下去:

这时下一个要吃的位置是第 行第 列(即绿色框出的位置),,所以 Lucia 会停止。最终吃掉了 颗草莓。

对于样例 2,Lucia 会先吃掉如下红色框出的位置:

,她会继续吃下去。然而剩余的位置数量少于 ,因此她会全部吃完。最终吃掉了所有的 颗草莓。

数据范围

对于 的数据,保证

对于另外 的数据,保证

对于 的数据,保证