思路过程
题目要求求出 需要涂色区域的最少数量,相当于两个色块之间的最短距离,这里的距离是指|xi-xj|+|yi-yj|
代码
#include<iostream>
#include<queue>
#include<cstring>
#include<math.h>
using namespace std;
const int N=55;
int n,m;
char g[N][N];
bool st[N][N];
int ans=1e5;
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
typedef pair<int,int>PII;
vector<PII> points[2];
void bfs(int x,int y,vector<PII> &point){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto now=q.front();
q.pop();
point.push_back({now.first,now.second});
for(int i=0;i<4;i++){
int a=now.first+dx[i],b=now.second+dy[i];
if(a<0||b<0||a>=n||b>=m) continue;
if(g[a][b]=='.'||st[a][b]==true) continue;
st[a][b]=true;
q.push({a,b});
}
}
}
int main(){
cin>>n>>m;
memset(g,'.',sizeof g);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) cin>>g[i][j];
}
int k=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(st[i][j]==false&&g[i][j]=='X'){
bfs(i,j,points[k++]);
}
}
}
for(auto a:points[0]){
for(auto b:points[1]){
ans=min(ans,abs(a.first-b.first)+abs(a.second-b.second));
}
}
cout<<ans-1;
return 0;
}