UVA 10502 - Counting Rectangles

Problem link

Keyword: DP

Algorithm:

The simplest way to find the answer requires O(N^6) time complexity and that's too slow for N=100.
However, we can use DP technique to achieve O(N^4).
Finding all squares whose upper left corner is at (i, j), and run through each line.
If the cell is 1, go on and add 1 to the answer, and break otherwise.
If break at last step, then don't run the whole line, and run to that column instead because we need the rectangle to be all 1s.

Code:

#include<cstdio>
const char on = '1', off = '0';

int main()
{
    int h, w;

    while( scanf( "%d %d\n", &h, &w ) == 2 )
    {
        char field[ h ][ w+1 ];
        int ans = 0;
        for( int i = 0; i < h; ++i )
            gets( field[ i ] );
        for( int i = 0; i < h; ++i )
            for( int j = 0; j < w; ++j )
                if( field[ i ][ j ] == on )
                {
                    int len = w;
                    for( int m = i; m < h; ++m )
                        for( int n = j; n < len; ++n )
                            if( field[ m ][ n ] == on )
                                ++ans;
                            else
                            {
                                len = n;
                                break;
                            }
                }
        printf( "%d\n", ans );
    }
    return 0;
}