orz,这题调了挺久的代码才ac。
那么,来简单说下思路,首先我们可以先用dfs划分连通块,标记出哪一个点属于哪一个连通块,就比如没斑点的地方的连通块就是0,靠左边的斑点连通块就是1,靠右边的斑点连通块为2。
然后,我们可以任意选择一个连通块bfs其中的每一个点并将其扩展记录距离,最后当遍历到了另一个连通块时就停止遍历然后记录距离并更新最小值,最后输出最小值就行(注意题目问的是需要染上多少个点,所以最终结果是距离减一)。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 60;
int n,m;
char a[N][N];
int st[N][N],p[N][N],d[N][N];
int res=0x3f3f3f3f,cnt=1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x,int y)
{
if(x<1||x>n||y<1||y>m||a[x][y]=='.'||st[x][y]) return;
st[x][y]=1;
p[x][y]=cnt;
dfs(x+1,y);
dfs(x,y+1);
dfs(x-1,y);
dfs(x,y-1);
}
void bfs(int x,int y)
{
memset(d,0,sizeof d);
queue<PII> q;
q.push({x,y});
st[x][y]=1;
d[x][y]=0;
while(q.size())
{
auto t=q.front();q.pop();
for(int i=0;i<4;i++)
{
int x1=t.first+dx[i],y1=t.second+dy[i];
if(x1<=n&&x1>=1&&y1<=m&&y1>=1&&!st[x1][y1]&&p[x1][y1]!=1)
{
d[x1][y1]=d[t.first][t.second]+1;
if(p[x1][y1]==2)
{
res=min(res,d[x1][y1]);
//cout<<x<<' '<<y<<' '<<d[x1][y1]<<endl;
//cout<<res<<endl;
return;
}
q.push({x1,y1});
st[x1][y1]=1;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]!='.'&&!st[i][j])
{
dfs(i,j);
cnt++;
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<p[i][j];
cout<<endl;
}
cout<<endl;
memset(st,0,sizeof st);*/
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(p[i][j]==1)
{
memset(st,0,sizeof st);
bfs(i,j);
}
}
/*bfs(3,7);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<d[i][j];
cout<<endl;
}
cout<<endl<<res-1<<endl;*/
cout<<res-1<<endl;
return 0;
}