Submission #1204072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204072		12345678	Zoo (COCI19_zoo)	C++20	110 / 110	38 ms	5448 KiB

zoo

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, m, di[4]={1, 0, 0, -1}, dj[4]={0, 1, -1, 0}, c[100], cur, ans, vs[nx][nx];
char mp[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1 ;i<=n; i++) for (int j=1; j<=m; j++) cin>>mp[i][j];
    c['T']=0;
    c['B']=1;

    cur=c[mp[1][1]];
    queue<pair<int, int>> q, nq;
    vs[1][1]=1;
    q.push({1, 1});
    while (!q.empty())
    {
        ans++;
        while (!q.empty())
        {
            auto [i, j]=q.front();
            q.pop();
            for (int k=0; k<4; k++)
            {
                int ni=i+di[k], nj=j+dj[k];
                if (vs[ni][nj]) continue;
                vs[ni][nj]=1;
                if (mp[ni][nj]!='B'&&mp[ni][nj]!='T') continue;
                if (c[mp[ni][nj]]==cur) q.push({ni, nj});
                if (c[mp[ni][nj]]==!cur) nq.push({ni, nj});
            }
        }
        cur=!cur;
        //cout<<"debug "<<nq.size()<<'\n';
        q=nq;
        while (!nq.empty()) nq.pop();
    }
    cout<<ans;
}

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