#P4945. 稀疏矩阵

稀疏矩阵

【例5.10】稀疏矩阵

题目描述

n×mn\times m 矩阵中大部分元素是 00 的矩阵称为稀疏矩阵。假设有 kk 个非 00 元素,则可把稀疏矩阵用 k×3k\times 3 的矩阵简记之,其中第一列是行号,第二列是列号,第三列是该行、该列下的非零元素的值。

例如,矩阵

0 0 0 5
0 2 0 0
0 1 0 0

可以简记为

1 4 5
2 2 2
3 2 1

其中第一行表示第 11 行第 44 列的数是 55。

试编程读入一个稀疏矩阵,把它转换成简记形式并输出。

输入格式

第一行为 nn 和 mm(1≤n≤1001\le n\le 100,1≤m≤1001\le m\le 100),nn 为行数,mm 为列数。

接下来是一个 n×mn\times m 的矩阵,矩阵中每个元素都是满足 0≤aij<10000\le a_{ij}<1000 的整数。

输出格式

输出稀疏矩阵的简记形式:

  • 第一行输出 nn、mm、kk,相邻两数之间用一个空格隔开;
  • 接下来 kk 行,按行优先顺序(先按行号从小到大,同一行再按列号从小到大)每行输出一个非零元素的三元组 (i,j,v)(i,j,v),表示第 ii 行第 jj 列的值为 vv,相邻两数之间用一个空格隔开;
  • 若 k=0k=0,则只输出第一行。

样例输入

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

样例输出

3 5 4
1 5 5
2 3 4
3 1 1
3 5 1