In some tests there appears the problem of finding the number of rectangles (or circles, or triangles, ...) of different sizes in a figure. We consider the problem of counting rectangles (including squares) in a rectangular board.

Given a rectangular board with n rows and m columns, with valid possitions marked with 1 and non valid possitions marked with 0,  we want to count the number of rectangles (including squares) in the board formed by squares marked with 1.

The Input

The input will consist of a series of problems, with each problem in a serie of lines. In the first and second lines the rows (n) and columns (m) of the board are indicated, in the next n lines the board in represented, with a row of the board in each line, and m 0 or 1 (without spaces) in each line. When the input of a problem finishes the next problem begins in the next line. The input finishes when 0 appears as the dimension of the board. Both dimensions of the board are less than or equal to 100.

The Output

The solution of each problem appears in a line, without separation between lines. For example, in the board

11

01

the rectangles are:

1-

--

-1

--

--

-1

11

--

-1

-1

Sample Input

2

2 

11

01

4

3

110

101

111

011 

0

Sample Output

5

22 

做法 : O(N^3)

求更快解法！

#include <stdio.h>

int main() {
    int n, m, i, j, k;
    char map[101][101];
    while(scanf("%d", &n) == 1 && n) {
        scanf("%d", &m);
        for(i = 0; i < n; i++)
            scanf("%s", &map[i]);
        int ans = 0, length, width, tmp;
        for(i = 0; i < n; i++) {
            int sum[101] = {};
            for(j = i; j < n; j++) {
                for(k = 0; k < m;  k++) {
                    sum[k] += map[j][k]-'0';
                    if(k == 0 || tmp != length*width)
                        tmp = 0, length = 0;
                    tmp += sum[k];
                    length++, width = j-i+1;
                    if(tmp == length*width)
                        ans += length;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}