C - Digital Graffiti Atcoder Beginner Contest 191 Code with Explanation

Problem Link

Explanation: We need to find number of sides, if  all '#' creates a polygon itself. For this purpose we need to find number of sides of this shape. Lets find if a cell is a side or not.

    1    2    3    4
1    .    .    .    .

2    .    #    #    .

3    .    #    #    .

4    .    .    .    .

Observations: If 4 adjacent cells has odd number of '#' it will contain a side of polygon. If a cell is (i,j) we will count '#' in cells (i,j),(i+1,j),(i+1,j+1),(i,j+1) for cell i,j.

for (1,1) >> Number of #  is 1 at(2,2)

for(1,2)>> Number of # is 2 at(2,2 and 2,3)

for(1,3)>> Number of # is 1 at(2,3)

...

...

...

In this way we will get the number of sides of the polygon.

Code

void solution(){
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    int ans=0;
    for(int i=0;i<h-1;i++){
        for(int j=0;j<w-1;j++){
            int cnt=0;
            if(s[i][j]=='#')cnt++;
            if(s[i+1][j]=='#')cnt++;
            if(s[i+1][j+1]=='#')cnt++;
            if(s[i][j+1]=='#')cnt++;
            if(cnt%2!=0)ans++;
        }
    }
    cout << ans << endl;
}