题目描述

题目描述 某大会议室有 N 行 M 列的座位，开会时发现有些座位是空的，但每个人都只关注在他 左前方的缺席人数（这次包括同行的左边和自己）。现在想知道每个座位关注到多少座位是空的。

例如： N=3 , M=4 ,下面格子中 1 表示有人， 0 表示空。

1 0 1 1
1 1 0 0
0 1 1 1

答案为：

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

输入格式

第一行 2 个正整数： N 和 M ，范围在 [1,100] 。 下面 N 行，每行 M 个整数： 0 或 1 。

输出格式

N 行，每行 M 个整数。

样例

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

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

优化分析

进一步分析，可以发现，方法二程序中计算一列的运算也是可以省略的！一列和 = (sum[i-1][j] - sum[i-1][j-1] ) + a[i][j]


这样程序的算法就可以优化到 O ( N^2 ) 了。