赞
踩
#include<iostream> #include<cstring> #include<algorithm> #include<vector> //flood fill algorithm //曼哈顿距离 //dfs #define x first #define y second using namespace std; const int N = 55; typedef pair<int ,int > PII; char g[N][N]; int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; vector<PII>points[2];//二维数组,因为一共只有两个斑点 int n,m; void dfs(int x,int y,vector<PII>& ps) { g[x][y]='.'; ps.push_back({x,y}); for(int i = 0; i < 4; i++)//对于每个点枚举四个方向 { int a = x + dx[i], b = y + dy[i]; // if(g[a][b] == 'X') if(a>= 0 && a<n && b>=0 && b< m&& g[a][b]=='X')//在图内并且该点还为‘X’ dfs(a, b, ps); } } int main() { cin>>n>>m; for(int i = 0 ; i < n ; i ++) cin>> g[i]; for(int i = 0 , k = 0; i < n; i++) { for(int j = 0 ; j < m; j++) { if(g[i][j] == 'X') dfs(i,j,points[k++]); } } int res = 1e8; /* for(int i = 0 ; i<points[0].size(); i++) { for(int j = 0; j<points[1].size(); j++) { res = min(res, abs(points[0][i].x-points[1][j].x)+abs(points[0][i].y-points[1][j].y)-1); } } */ for (auto& a: points[0]) for (auto& b: points[1]) res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1); cout << res << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。