#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, vector <int> (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, vector <int> (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 time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |