Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1443
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’. 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. 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 -- 11 -1 -- -- -1 -- -1
Sample Input 2 2 11 01 4 3 110 101 111 011 0
Sample Output 5 22
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,v;
char grid[101];
while(cin >> n, n){
cin >> m;
vector < vector<int>> dpSum(n+1,vector<int>(m+1));
for(int i=1;i < =n;i++) {
scanf("%s",grid);
for(int j=1;j < =m;j++){
dpSum[i][j] = dpSum[i-1][j] + dpSum[i][j-1] - dpSum[i-1][j-1];
dpSum[i][j] += (grid[j-1]-'0');
}
}
int res = 0;
//foreach starting coordinate topleft
for(int i=1;i < =n;i++){
for(int j=1;j < =m;j++){
//foreach ending coordinate btmright
for(int k=i;k < =n;k++){
for(int l=j;l < =m;l++){
int fullSquare = (k-i+1)*(l-j+1);
int filledAmt = dpSum[k][l] - (dpSum[k][j-1] + dpSum[i-1][l] - dpSum[i-1][j-1]);
if(fullSquare == filledAmt) res++;
}
}
}
}
cout << res << endl;
}
}Input
11
01
4
3
110
101
111
011
0
Output
22
Demonstration
UVA Online Judge solution - 10502-Counting Rectangles - UVA Online Judge solution in C,C++,java