제출 #1370498

#제출 시각아이디문제언어결과실행 시간메모리
1370498ziyad_alharbiZoo (COCI19_zoo)C++20
0 / 110
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define gcd __gcd
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,ans1=0,ans2=0;
    cin>>n>>m;
    vector<array<int,2>>vc[n+5][m+5];
    string s[n+5];
    int vs[n+5][m+5]={};
    for(int x=0;x<n;x++)cin>>s[x];
    bool b=0,t=0;
    for(int x=0;x<n;x++)for(int y=0;y<m;y++)
    {
        if(s[x][y]=='B')b=1;
        if(s[x][y]=='T')t=1;

        if(x!=n-1&&s[x+1][y]==s[x][y])
        {
            vc[x][y].push_back({x+1,y});
            vc[x+1][y].push_back({x,y});
        }
        if(y!=m-1&&s[x][y+1]==s[x][y])
        {
            vc[x][y].push_back({x,y+1});
            vc[x][y+1].push_back({x,y});
        }
    }
    for(int x=0;x<n;x++)for(int y=0;y<m;y++)if(!vs[x][y]&&s[x][y]=='T')
    {
        ans1++;
        queue<array<int,2>>q;
        q.push({x,y});
        while(q.size())
        {
            auto [X,Y]=q.front();
            q.pop();
            if(vs[X][Y])continue;
            vs[X][Y]=1;
            for(auto [i,j]:vc[X][Y])if(!vs[i][j])q.push({i,j});
        }
    }
    for(int x=0;x<n;x++)for(int y=0;y<m;y++)if(!vs[x][y]&&s[x][y]=='B')
    {
        ans2++;
        queue<array<int,2>>q;
        q.push({x,y});
        while(q.size())
        {
            auto [X,Y]=q.front();
            q.pop();
            if(vs[X][Y])continue;
            vs[X][Y]=1;
            for(auto [i,j]:vc[X][Y])if(!vs[i][j])q.push({i,j});
        }
    }
    cout<<min(ans1+(s[0][0]=='B')+b,ans2+(s[0][0]=='T')+t)<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…