E

题解

看到大部分人都是dfs或bfs搜索做的，这里给一个并查集的方法：对于边缘处的'.'，与一个extra=m*n连接；对于不在边缘处的'.'，merge其上下左右的'.'和该点。最后遍历，遍历到不与extra连通的'.'，ans++。再把'#'加到答案中，

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
vector<int> parent;
int find(int u)
{
    if(parent[u]==u) return u;
    return parent[u]=find(parent[u]);
}
void merge(int u,int v)
{
    int ru=find(u),rv=find(v);
    if(ru==rv) return;
    parent[ru]=rv;
}
int trans(int i,int j)
{
    return i*m+j;
}
int drow[4]={0,0,1,-1};
int dcol[4]={1,-1,0,0};

int main(void)
{
    cin>>n>>m;
    vector<vector<char> > maze(n,vector<char>(m));
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        {
            char ch;
            cin>>ch;
            maze[i][j]=ch;
        }
    int extra=m*n;
    parent.resize(m*n+1);
    for(int i=0;i<=m*n;++i)
        parent[i]=i;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(maze[i][j]=='.')
            {
                if(i==0||i==n-1||j==0||j==m-1)
                    merge(trans(i,j),extra);
                else
                {
                    for(int k=0;k<4;++k)
                    {
                        int nextrow=i+drow[k];
                        int nextcol=j+dcol[k];
                        if(maze[nextrow][nextcol]=='.')
                            merge(trans(i,j),trans(nextrow,nextcol));
                    }
                }
            }
    int ans=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if((maze[i][j]=='.'&&find(trans(i,j))!=find(extra))||maze[i][j]=='#')
                ans++;
    cout<<ans<<endl;
    return 0;
}