暴力破解思路如下: 1、先确定左上角的顶点,从左到右遍历行列数(行数假设为m,列数假设为n),此时确定一个矩形的左上角的顶点。记录该顶点为(i, j)。 2、以(i, j)为矩形的左上角顶点,从j+1遍历到n,如果点为0,则继续,如果为1,则进行下一步。假设为1的点为(i,k)。 3、以(i, j)为矩形的左上角顶点,从i+1遍历到m-i,如果遍历到的点为0,则继续,如果为1,则进行下一步。假设为1的点为(p,j)。 4、以(i, j)为矩形的左上角顶点,从j+1遍历到n-j,如果遍历到的点为0,则继续,如果为1,则矩形数量增加1。此时为1的点为(p,k)。 5、重复1-4,直至遍历完成。 该种暴力算法,用C++编写可以AC,Python提交超时。
该题解题思路如下: 1、同时遍历两行,固定其中一行(i行),另一行从i+1行开始遍历,并初始化ct=0 2、从左往右开始进行列遍历,如果两行和当前列的所有交点都是1,此时计数ct+1 3、此时,ct即为交点均为1的数字情况,此时矩形数量为ct*(ct-1)/2。逐次累加就好。
Python可以AC: