【编程练习】牛牛的方格图

题目来源：牛客小白月赛47，第E题【前4题都比较简单】

题目描述

题解

思路：
1）首先需要想清楚，如何框定某种颜色的覆盖范围？以下列方格图为例：
1 3 3 4
3 2 1 4
6 3 3 4
对于颜色3而言，一共有2种典型的覆盖方式：从(2,1)到(3,3) 和 从(2,1)到(3,1)；这两种覆盖方式涵盖了颜色3所能覆盖的最大面积。

从中可以发现，某个颜色所能覆盖的最大范围，其实由该颜色的min_x、min_y、max_x、max_y决定；

2）如何标记覆盖范围？覆盖范围其实由以(min_x,min_y)为左上角和(max_x,max_y)为右下角框定的矩形表示。

遍历标记必然会超时，这里学习到了一个新姿势——前缀和。

简单来说，对一维数组而言，a[i]的前缀和等于sum(a[:i+1])，即前i个元素之和，那么就有递推式：prefix[i] = prefix[i-1]+a[i]；
对二维数组而言，该递推式就演化为：prefix[i,j] = prefix[i-1,j]+prefix[i,j-1-prefix[i-1,j-1]+a[i,j]；
了解完前缀和，就可以用前缀和进行覆盖范围的标记。

思想如下：根据前缀和的性质可知，当点(min_x,min_y)的前缀和+1后，点(min_x,min_y)之后的所有点的前缀和都会+1；同理，通过对特定点的前缀和-1，就能标记出特定的矩阵；
最后，求解每个元素的前缀和，如果该点的前缀和为0，就说明该点未被覆盖。

代码：

def main():
    n,m = map(int,input().split())
    prefix_sum = [[0]*(m+2) for i in range(n+2)]
    col_dict = [0]*int(1e6+10)
    for i in range(1,n+1):
        col = [int(j) for j in input().split()]
        for j in range(1,m+1):
            if col_dict[col[j-1]]==0:
                col_dict[col[j-1]]=[i,j,i,j] # 0:min_x,1:min_y,2:max_x,3:max_y
            else:
                tmp = col_dict[col[j-1]]
                col_dict[col[j-1]]=[min(i,tmp[0]),min(j,tmp[1]),max(i,tmp[2]),max(j,tmp[3])]
    for v in col_dict:
        if v != 0 and (v[0]!=v[2] or v[1]!=v[3]):
            prefix_sum[v[0]][v[1]]+=1
            prefix_sum[v[2]+1][v[3]+1]+=1
            prefix_sum[v[2]+1][v[1]]-=1
            prefix_sum[v[0]][v[3]+1]-=1
    ans = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            prefix_sum[i][j] += prefix_sum[i-1][j]+prefix_sum[i][j-1]-prefix_sum[i-1][j-1]
            if prefix_sum[i][j] == 0:
                ans+=1
    print(ans)
    return

if __name__ == '__main__':
    main()

但这个题的python版会超时，还是得用C/C++，如下：

#include 
int main(){
    int n,m,c,ans=0;
    int prefix_sum[1005][1005]={0},col[1000005][4]={0};
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&c);
            if(col[c][0]==0){
                col[c][0]=i;col[c][1]=j;col[c][2]=i;col[c][3]=j;
                // 0:min_x; 1:min_y; 2:max_x; 3:max_y;
            }
            else{
                col[c][0]=i<col[c][0]?i:col[c][0];
                col[c][1]=j<col[c][1]?j:col[c][1];
                col[c][2]=i>col[c][2]?i:col[c][2];
                col[c][3]=j>col[c][3]?j:col[c][3];
//                 col[c][0]=min(i,col[c][0]);col[c][1]=min(j,col[c][1]);
//                 col[c][2]=max(i,col[c][2]);col[c][3]=max(j,col[c][3]);
            } 
        }
    }
    for(int i=1;i<=1000000;i++){
        if(col[i][0]!=0 && (col[i][0]!=col[i][2] || col[i][1]!=col[i][3])){
            prefix_sum[col[i][0]][col[i][1]]++;
            prefix_sum[col[i][2]+1][col[i][3]+1]++;
            prefix_sum[col[i][2]+1][col[i][1]]--;
            prefix_sum[col[i][0]][col[i][3]+1]--;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            prefix_sum[i][j]+=prefix_sum[i-1][j]+prefix_sum[i][j-1]-prefix_sum[i-1][j-1];
            if(prefix_sum[i][j]==0){
                ans++;
            }
        }
    }
    printf("%d",ans);
    return 0;
}