Submission #206608

#	Time	Username	Problem	Language	Result	Execution time	Memory
206608		stefdasca	Zoo (COCI19_zoo)	C++14	110 / 110	53 ms	3448 KiB

zoo

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int n, m;
char c[1002][1002];
bool blocked[1002][1002];
int ans = 0;
int ox[] = {-1, 0, 1, 0};
int oy[] = {0, 1, 0, -1};
bool verif(int L, int C)
{
    return (L >= 1 && L <= n && C >= 1 && C <= m);
}
void lee(int L, int C)
{
    char init = c[L][C];
    c[L][C] = 'F';
    deque<pair<int, int> >d, d2;
    d.pb({L, C});
    while(!d.empty() || !d2.empty())
    {
        ++ans;
        while(!d.empty())
        {
            pair<int, int> poz = d[0];
            d.pop_front();
            for(int i = 0; i <= 3; ++i)
            {
                int X = poz.fi + ox[i];
                int Y = poz.se + oy[i];
                if(!verif(X, Y))
                    continue;
                if(c[X][Y] == 'F' || c[X][Y] == '*')
                    continue;
                if(blocked[X][Y])
                    continue;
                if(c[X][Y] == init)
                {
                    d.push_back({X, Y});
                    blocked[X][Y] = 1;
                }
                else
                {
                    d2.push_back({X, Y});
                    blocked[X][Y] = 1;
                }
            }
        }
        if(init == 'B')
            init = 'T';
        else
            init = 'B';
        swap(d, d2);
        for(int i = 0; i < d.size(); ++i)
        {
            pair<int, int> poz = d[0];
            c[poz.fi][poz.se] = 'F';
            blocked[poz.fi][poz.se] = 0;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> (c[i] + 1);
    lee(n, m);
    cout << ans;
    return 0;
}

Compilation message (stderr)

zoo.cpp: In function 'void lee(int, int)':
zoo.cpp:91:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < d.size(); ++i)
                        ~~^~~~~~~~~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65