codeforces Looksery Cup 2015 D. Haar Features

The first algorithm for detecting a face on the image working in realtime was developed by Paul Viola and Michael Jones in 2001. A part of the algorithm is a procedure that computes Haar features. As part of this task, we consider a simplified model of this concept.

Let‘s consider a rectangular image that is represented with a table of size n?×?m. The table elements are integers that specify the brightness of each pixel in the image.

A feature also is a rectangular table of size n?×?m. Each cell of a feature is painted black or white.

To calculate the value of the given feature at the given image, you must perform the following steps. First the table of the feature is put over the table of the image (without rotations or reflections), thus each pixel is entirely covered with either black or white cell. The valueof a feature in the image is the value of W?-?B, where W is the total brightness of the pixels in the image, covered with white feature cells, and B is the total brightness of the pixels covered with black feature cells.

Some examples of the most popular Haar features are given below.

#include #include #include #include #include #include #include #include #include using namespace std; char s[105][105]; int map[105][106]; int main() { int n,m,i,j,c,ans,r,num; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i=0;i--){ for(j=m-1;j>=0;j--){ if(s[i][j]=='W'){ if(map[i][j]!=1){ num++; ans=1-map[i][j]; for(r=i;r>=0;r--){ for(c=j;c>=0;c--){ map[r][c]+=ans; } } } } else if(s[i][j]=='B'){ if(map[i][j]!=-1){ num++; ans=map[i][j]+1; for(r=i;r>=0;r--){ for(c=j;c>=0;c--){ map[r][c]-=ans; } } } } } } printf("%d\n",num); } return 0; }