UVa 10502

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

Given an n*m graph with each cell containing either 0 or 1, count how many rectangles can be formed by using the 1s

Gotchas[edit]

Precalculate array sum[i][j],the numbers of 1 from graph[1][1] to graph[i][j] (index starting from 1 would be easier to deal with around edges) using sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] + graph[i][j]-'0'

Then we could iterate through all possible rectangle in the given size in O(n^4) :


Implementations[edit]

for(int x1 = 1; x1 <= n; x1 ++)
    for(int y1 = 1; y1 <= m; y1 ++)
        for(int x2 = x1; x2 <= n; x2 ++)
	    for(int y2 = y1; y2 <= m; y2 ++)
		if((x2-x1+1)*(y2-y1+1) == arr[x2][y2]-arr[x2][y1-1]-arr[x1-1][y2]+arr[x1-1][y1-1])
		    cnt ++;

Input[edit]

2
2 
11
01
4
3
110
101
111
011 
0

Output[edit]

5
22