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; }