题目描述
题目中只是两个斑点,如果有多个呢?
下面就是多个的解法,bfs求最短路+dfs合并分区
思路就是枚举每个’.’ ,从每个点去连接所有联通块,找出最小的。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl '\n'
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)
#define For(i,x,n) for(int i=x;i<=n;i++)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define int long long
#define all(x) x.begin(),x.end()
//typedef unsigned long long ULL;//自动取模 字符哈希 取前缀 h[r]-h[l-1]*p[r-h+1]
typedef pair<int, int > PII;
const int N = 2e5 + 10, M = 1e6 + 10, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double pai = acos(-1.0);
char g[100][100];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int ans;
bool st[100][100];
int n,m;
int dist[100][100];
void dfs(int x,int y,queue<PII > &q)
{
q.push({x,y});
dist[x][y]=0;
// cout<<x<<' '<<y<<endl;
st[x][y]=true;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(st[xx][yy]) continue;
if(g[xx][yy]=='.') continue;
dfs(xx,yy,q);
}
}
vector<PII> v;
void bfs(int bx,int by,queue<PII> &q)
{
q.push({bx,by});
dist[bx][by]=0;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(st[x][y]) continue;
if(g[x][y]=='.')
{
dist[x][y]=dist[t.first][t.second]+1;
st[x][y]=true;
q.push({x,y});
}else //如果找到另一个联通区域 就把该联通区全加入队列 然后继续遍历
{
ans+=dist[t.first][t.second];//记录答案
//cout<<t.first<<' '<<t.second<<' '<<ans<<endl;
// while(q.size()) q.pop();
// cout<<t.first<<' '<<t.second<<' '<<dist[t.first][t.second]<<endl;
dfs(x,y,q);
}
}
}
}
void solve()
{
cin>>n>>m;
For(i,1,n)
For(j,1,m) cin>>g[i][j];
bool ok=false;
int res=INF;
For(i,1,n)
For(j,1,m)
{
if(g[i][j]=='.')
{
st[i][j]=true;
queue<PII> q;
bfs(i,j,q);
memset(dist,0,sizeof dist);
memset(st,false,sizeof st);
res=min(res,ans+1);
ans=0;
}
}
cout<<res<<endl;
}
signed main()
{
ios
solve();
}
/*
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX....X.XXX..
.......X...XX...
.........XXX....
*/