Submission #1124469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124469		doducanh	Zoo (COCI19_zoo)	C++20	110 / 110	86 ms	5448 KiB

zoo

///roadtoVOI2025
///enjoythejourney
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
const int maxn=1005;
char a[maxn][maxn];
int vst[maxn][maxn];
int n,m;
bool check(int x,int y)
{
    return (1<=x&&x<=n&&1<=y&&y<=m);
}
void sol()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    queue<ii>q;
    q.push({1,1});
    vst[1][1]=1;
    int res=1;
    while(q.size()){
        vector<ii>vv;
        while(q.size())
        {
            int u=q.front().fi;
            int v=q.front().se;
            q.pop();
            for(int i=0; i<4; i++)
            {
                int nu=u+dx[i];
                int nv=v+dy[i];
                if(!check(nu,nv))continue;
                if(!vst[nu][nv])
                {
                    if(a[nu][nv]==a[u][v])
                    {
                        vst[nu][nv]=vst[u][v];
                        q.push({nu,nv});
                    }
                    else if(a[nu][nv]!='*')vv.push_back({nu,nv});
                }
            }
        }
        if(vv.size())res++;
        for(ii pp:vv){
            vst[pp.fi][pp.se]=res;
            q.push(pp);
        }
    }
    cout<<res;
}
signed main(void)
{
//    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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