oj.uz

Submission #209337

# Submission time Handle Problem Language Result Execution time Memory
209337 2020-03-13T20:14:03 Z papa Emacs (COCI20_emacs) C++14
50 / 50
 6 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

//za svaku komponentu vidimo da li je u obliku pravougaonika 
//koristimo bfs da nadjemo 'temena' pravougaonika

int n,m;
int mat[105][105];
int vis[105][105];
int cnt = 0;
int sol;
int por[] = {1,-1,0,0};
int pok[] = {0,0,1,-1};

void bfs(int sr,int sk)
{
    queue<pair<int,int > >  q;
    q.push({sr,sk});
    vis[sr][sk] = 1;
    cnt = 0;
    int rmaks = sr;
    int rmin = sr;
    int kmaks = sk;
    int kmin = sk;

    while(!q.empty())
    {
        pair<int,int> p  =q.front();
        q.pop();
        cnt++;
        int tr = p.first; rmaks = max(rmaks,tr); rmin = min(rmin,tr);
        int tk = p.second; kmaks = max(kmaks,tk); kmin = min(kmin,tk);
        for(int i=0;i<4;i++)
        {
            int nr = tr+por[i];
            int nk = tk+pok[i];
            if(nr>=1 && nr<=n && nk>=1 && nk<=m && !vis[nr][nk] && mat[nr][nk])
            {
                vis[nr][nk] = 1;
                q.push({nr,nk});
            }
        }
    }

    if((rmaks-rmin+1)*(kmaks-kmin+1) == cnt) sol++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);

    cin >> n >> m;

    for(int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        for(int j=0;j<m;j++)
        {
            if(s[j]=='*') mat[i][j+1] = 1;
            else mat[i][j+1] = 0;
        }
    }

    sol = 0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j] && mat[i][j])
            {
                bfs(i,j);
            }
        }
    }

    cout << sol;

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct