---

借鉴大佬的思路https://blog.csdn.net/Jaster_wisdom/article/details/52153685

 

首先思考在一维数组中，若想求元素和大于等于K的子数组的最小长度，可以怎么做？

可以使用两个指针start，end，初始时都指向0。end后移直到sum>=K，然后start开始后移，直到sum<K时start停止后移，end开始后移...

如此往复直到end>=一维数组长度；在这个过程中，当sum>=K时，每次start后移之后，判断sum是否仍满足条件，并更新最小长度res=min(res,end-start+1)

 

在本题中，可以将任意两列i,j之间的所有列合并，降维成一维数组，然后求其最小长度，之后再用其最小长度temp乘以(j-i+1)即为子矩阵的个数。

如此遍历完整个矩阵，保留所求子矩阵即可。

 

细节1：当整个矩阵的和sum<K时，直接输出-1

        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
            {
                cin>>matrix[i][j];
                sum+=matrix[i][j];
            }
        if(sum<K) cout<<-1<<endl;

 

细节2：在main函数中遍历时，i表示起始列，j表示终止列，所以i的枚举范围是0~M，j的枚举范围是i~M

            for(int i=0;i<M;i++)
                for(int j=i;j<M;j++)
                {
                    fill(num,num+MAXN,0);
                    merge(i,j);
                    int temp=FindShortest();
             ...