题目描述
略显麻烦的搜索,思路是这样先用dfs把一部分联通块x染色成1,再枚举每个‘1’点的坐标与每个剩余‘x’的坐标,用曼哈顿距离去计算两点坐标值,取最小值就行。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cstdio>
#include <cmath>
using namespace std;
int stepx[5]={0,1,-1,0,0};
int stepy[5]={0,0,0,1,-1};
const int N = 51;
int n,m,ans=800;
char maps[N][N];
int tempx,tempy;
void dfs(int x,int y)
{
maps[x][y]='1';
for(int i=1;i<=4;i++)
{
int dx=x+stepx[i];
int dy=y+stepy[i];
if(dx>0&&dy>0&&y<=m&&x<=n&&maps[dx][dy]=='X')
{
dfs(dx,dy);
}
}
}
void check(int x,int y)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(maps[i][j]=='X')
{
int t=abs(x-i)+abs(y-j)-1;
if(ans>t)
{
ans=t;
//cout<<ans<<" ";
//cout<<x<<" "<<y<<" "<<i<<" "<<j<<endl;
}
}
}
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>maps[i][j];
if(maps[i][j]=='X')
{
tempx=i;
tempy=j;
}
}
}
dfs(tempx,tempy);
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<maps[i][j];
cout<<endl;
}*/
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(maps[i][j]=='1')
{
check(i,j);
maps[i][j]='.';//把1覆盖
}
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<maps[i][j];
}
cout<<endl;
}*/
cout<<ans<<endl;
return 0;
}