Submission #1307643

#TimeUsernameProblemLanguageResultExecution timeMemory
1307643JelaByteEngineerTracks in the Snow (BOI13_tracks)C++20
0 / 100
2135 ms884528 KiB
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> g1, g2;
void dfs (int node, vector <bool> &vis)
{
    vis[node]=true;
    for (auto i: g1[node])
    {
        if (!vis[i]) dfs(i, vis);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>n>>m;
    vector <vector <char>> mat(n, vector <char> (m));
    map <pair<int, int>, int> mapa1, mapa2;
    int cntu=0, cntf=0;
    for (int i=0; i<n; i++)
    {
        string s; cin>>s;
        for (int j=0; j<m; j++)
        {
            mat[i][j]=s[j];
            if (s[j]!='.')
            {
                mapa1[{i, j}]=cntu;
                cntu++;
            }
            if (s[j]=='F')
            {
                mapa2[{i, j}]=cntf;
                cntf++;
            }
        }
    }
    g1.resize(cntu);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (mat[i][j]!='.')
            {
                if (i-1>=0 && mat[i-1][j]!='.')
                {
                    g1[mapa1[{i, j}]].push_back(mapa1[{i-1, j}]);
                }
                if (i+1<n && mat[i+1][j]!='.')
                {
                    g1[mapa1[{i, j}]].push_back(mapa1[{i+1, j}]);
                }
                if (j-1>=0 && mat[i][j-1]!='.')
                {
                    g1[mapa1[{i, j}]].push_back(mapa1[{i, j-1}]);
                }
                if (j+1<m && mat[i][j+1]!='.')
                {
                    g1[mapa1[{i, j}]].push_back(mapa1[{i, j+1}]);
                }
            }
        }
    }
    g2.resize(cntf);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (mat[i][j]!='.')
            {
                if (i-1>=0 && mat[i-1][j]!='.')
                {
                    g2[mapa2[{i, j}]].push_back(mapa2[{i-1, j}]);
                }
                if (i+1<n && mat[i+1][j]!='.')
                {
                    g2[mapa2[{i, j}]].push_back(mapa2[{i+1, j}]);
                }
                if (j-1>=0 && mat[i][j-1]!='.')
                {
                    g2[mapa2[{i, j}]].push_back(mapa2[{i, j-1}]);
                }
                if (j+1<m && mat[i][j+1]!='.')
                {
                    g2[mapa2[{i, j}]].push_back(mapa2[{i, j+1}]);
                }
            }
        }
    }
    vector <bool> vis1(cntu, false);
    vector <bool> vis2(cntf, false);
    int ans=0;
    for (int i=0; i<cntu; i++)
    {
        if (!vis1[i])
        {
            ans++;
            dfs(i, vis1);
        }
    }
    for (int i=0; i<cntf; i++)
    {
        if (!vis2[i])
        {
            ans++;
            dfs(i, vis2);
        }
    }
    cout<<ans<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...