《算法竞赛宝典》语言及算法入门(公开课程)

　　

　　【题目描述】稀疏数组（zip.cpp/c/pas）

　　所谓稀疏数组是指数组中大部分内容都没有被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并不影响数组中原有的内容值，可以采用一种压缩的方式来表示稀疏数组的内容。

　　例如，有一个大小为10×10的数组，内容如图所示：

　　可以看出，这个数组中只使用了5个元素，而其他的元素空间就被浪费了，为了节省空间，我们可以使用稀疏数组来表示这个数组，如图所示：

　　此数组的第一部分即第一行记录的是原数组的列数和行数及元素的使用个数。

　　此数组的第二部分所记录的是原数组中非零元素的行数、列数和元素值。

　　请自编一个程序，读入原始数组，输出压缩数组。

　　【输入格式】

　　输入文件为zip.in，输入数据第一行为N，M （N≤50，M≤50），即N行M列，以下N行为数组元素，保证非零个数不会超过全部原始的三分之一（话说这样压缩真的有效吗？）。

　　【输出格式】

　　输出文件为zip.out， 即稀疏数组。

　　【输入样例】

　　10 10

　　0 3 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　1 2 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 5 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 0 0 0

　　0 0 0 0 0 0 0 6 0 0

　　【输出样例】

　　10 10 5

　　0 1 3

　　3 0 1

　　3 1 2

　　5 6 5

　　9 7 6