#NH4540. NH.2014.04.数字方阵(matrix)
NH.2014.04.数字方阵(matrix)
题目描述
周末,爸爸妈妈带着楠楠去商场玩,正好碰上了商场在举办有奖竞答活动,而且根据问题的难度不同,奖品的价值也有不同。聪明爱动脑的楠楠挑了一个难度最大的问题来挑战自己。最后他赢得了丰厚的奖品和热烈的掌声。
这个问题是:在一个数字方阵中,随机放置了0~9的数字。我们把由数字1~9的组成的串称为非零串(不含0的数字串)。例如02303230 ,这组数据中有23 和323两种非零串。其中长度最长的非零串为323。
已知一个NM(1<=N,M<=1000)的数字方阵,求方阵第k行的最长非零串的长度。
如下图:在这个48的方阵中,第2行的最长非零串长度为3。
由于这个方阵太大了,很多人都不敢一试。这时候,楠楠拿出他的随身笔记本,编了一个程序,瞬间就秒杀了它!
如果是你,你能解决吗?
输入格式
输入数据有若干行。
第一行,有三个整数N、M(1<=N、M<=1000)和K(1<=K<=N),其中N、M分别表示这个数字方阵中行数和列数。K表示求数字方阵第K行的最长数字串长度。
接下来有N行,每行M个0~9的数字,每个数字间用一个空格隔开。
输出格式
输出第K行的最长非零串的长度。
样例
4 9 3
9 2 0 0 3 4 2 5 0
4 0 2 3 0 3 2 3 1
3 8 3 2 9 0 7 5 1
1 0 3 1 0 0 6 6 0
5