题目描述

题目描述 某大会议室有 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

优化分析

四重循环，时间复杂度为 O ( N^4 ) 。如果数据范围大一点，肯定会超时。计算中有大量的统计是重复的，比如：计算位置 (3,3) 时，就和计算位置(3,2)重复了！

程序如果记录下以前计算的结果，算法可以简单改进为 O ( N^3 ) 的。

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],sum[101][101];
int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);


	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			sum[i][j] = 填空(1);
				
			for(int ti=1;ti<=填空(2);ti++)
				sum[i][j] += 填空(3);

			printf("%d ",sum[i][j]);

		}
		printf("\n");
	}

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}